2, 3, 5, 11의 배수 & 유클리드 호제법

2와 5의 배수인지 알아보는 것은 쉽다. 끝이 짝수(0, 2, 4, 6, 8)인 경우와 5 또는 0인 경우이다.

3은 각 자리의 수를 더한 다음 3으로 나누어 떨어지면 3의 배수이다.
예를 들어
5928 = 5 * 1000 + 9 * 100 + 2 * 10 + 8
5928 = 5 * (999 + 1) + 9 * (99 + 1) + 2 * (9 + 1) + 8
5928 = (5 * 999 + 9 * 99 + 2 * 9) + ( 5 + 9 + 2 + 8)
5 + 9 + 2 + 8 = 24
3의 배수다.

11을 인수로 가지는 자연수를 판별하는 방법은 우선
99, 9999, ...
와 같이 9가 짝수개로 된 수가 11로 나누어 떨어지는 것은 분명하고 또
1001, 100001, ...
와 같이 짝수개 자리로 양 끝의 숫자가 1, 가운데 숫자가 모두 0인 수는 각각
1001 = 990 + 11, 100001 = 99990 + 11, ...
와 같이 되기 때문에 11로 나누어 떨어진다.
예를 들어
42834 = 4 * 10000 + 2 * 1000 + 8 * 100 + 3 * 10 + 4
42834 = 4 * (9999 + 1) + 2 * (1001 - 1) + 8 * (99 - 1) + 3 * (11 - 1) + 4
42834 = (4 * 9999 + 2 * 1001 + 8 * 99 + 3 * 11) + (4 - 2 + 8 - 3 + 4)
4 - 2 + 8 - 3 + 4 = 11
11의 배수다.

컴퓨터는 그냥해도 빠르지만 한번 위의 방법을 코드로 만들어봤다.

#include <stdio.h>                                                                 
#include <stdbool.h>                                                               
                                                                                   
bool is_multiple_two(int num);                                                     
bool is_multiple_three(int num);                                                   
bool is_multiple_five(int num);                                                    
bool is_multiple_eleven(int num);                                                  
                                                                                   
int main()                                                                         
{                                                                                  
    int number;                                                                    
    int multiple[4] = {0};                                                         
                                                                                   
    printf("Enter a number: ");                                                    
    scanf("%d", &number);                                                          
    printf("You put %d\n", number);                                                
                                                                                   
    if (multiple[0] = is_multiple_two(number)) {                                   
        printf("a multiple of two.\n");                                            
    }                                                                              
    if (multiple[1] = is_multiple_three(number)) {                                 
        printf("a multiple of three.\n");                                          
    }                                                                              
    if (multiple[2] = is_multiple_five(number)) {                                  
        printf("a multiple of five.\n");                                           
    }                                                                              
    if (multiple[3] = is_multiple_eleven(number)) {                                
        printf("a multiple of eleven.\n");                                         
    }                                                                              
    for (int i = 0; i < 4; i++)                                                    
    {                                                                              
        if (multiple[i])                                                           
            return 0;                                                              
    }                                                                              
    printf("not a multiple of two, three, five or eleven.\n");                     
                                                                                   
    return 0;                                                                      
}                                                                                  
                                                                                   
bool is_multiple_two(int num)                                                      
{                                                                                  
    while (num > 10)
        num %= 10;                                                              
    return num % 2 == 0 ? true : false;                                         
}                                                                               
                                                                                
bool is_multiple_five(int num)                                                  
{                                                                               
    while (num > 10)                                                            
        num %= 10;                                                              
    return num % 5 == 0 ? true : false;                                         
}                                                                               
                                                                                
bool is_multiple_three(int num)                                                 
{                                                                               
    int sum_each_digit = 0;                                                     
                                                                                
    while (num > 0) {                                                           
        sum_each_digit += num % 10;                                             
        num /= 10;                                                              
    }                                                                           
                                                                                
    return sum_each_digit % 3 == 0 ? true : false;                              
}                                                                               
                                                                                
bool is_multiple_eleven(int num)                                                
{                                                                               
    int sum_each_digit = 0;                                                     
    int digit = 1;                                                              
                                                                                
    while (num > 0)                                                             
    {                                                                           
        if (digit % 2)                                                          
            sum_each_digit -= num % 10;                                         
        else                                                                    
            sum_each_digit += num % 10;                                         
        num /= 10;                                                              
        digit++;                                                                
    }                                                                           
                                                                                
    return sum_each_digit % 11 == 0 ? true : false;                             
}

유클리드 호제법(Euclidean algorithm)

두 개의 양수 $a,\;b$의 최대공약수(gdc)를 구하는데 $a,\;b$를 소인수분해하면 된다.

이때, 만약 $r = 0\;$이라면, 즉 a가 b로 나누어떨어지면, b가 a와 b의 최대공약수이다.
또, 만약 $r\gt 0\,$이라면, 위의 식에서 $r = a - bq\,$이므로, $e\,$를 $a,\;b\,$의 임의의 공약수라 하면, 우변의 $a-bq\,$가 $e\,$로 나누어 떨어지고, 따라서 $r\,$이 $e\,$로 나누어 떨어진다. 그러므로 $e\,$는 $b\,$와 $r\,$의 공약수가 된다.
한편, $e'\,$를 $b,\,r\,$의 임의의 공약수라 하면, $a = bq \,+\,r\,$라는 식에서 $e'\,$는 $a\,$를 나누어떨어지게 하고, 따라서 $e'\,$는 $a,\,b\,$의 공약수가 된다.
이것으로 $a\,$와 $b\,$의 공약수는 $b\,$와 $r\,$의 공약수이고, 역으로 $b\,$와 $r\,$의 공약수는 $a\,$와 $b\,$의 공약수임을 알 수 있다.
따라서, $a,\,b\,$의 최대공약수 $=$ $b,\,r\,$의 최대공약수임을 알 수 있다.
다음에 $b\,$를 $r\,$로 나눈 나머지를 $r_1\,$라 하고, 위와 같은 형태로 $r_1=0\,$이라면 $r\,$이 $b\,$와 $r\,$의 최대공약수가 되고, $r_1\gt 0\,$이라면 $a,\,b\,$의 최대공약수 $=$ $b,\,r\,$의 최대공약수 $=$ $r,\,r_1\,$의 최대공약수가 된다.
위 방법을 나누어떨어질때까지 계속하면 나눗셈에 위해서 반드시 $a,\,b\,$의 최대공약수를 구할 수 있다.

#include <stdio.h>                                                                                  
                                                                                                       
int main(void)                                                                                         
{                                                                                                      
    int n1, n2;                                                                                        
    int a, b, r;                                                                                       
                                                                                                       
    printf("Put two numbers(e.g. 1, 2): ");                                                            
    scanf("%d, %d", &n1, &n2);                                                                         
                                                                                                       
    if (n1 < n2) {                                                                                     
        a = n2;                                                                                        
        b = n1;                                                                                        
    } else {                                                                                           
        a = n1;                                                                                        
        b = n2;                                                                                        
    }                                                                                                  
                                                                                                       
    do {                                                                                               
        r = a % b;                                                                                     
        a = b;                                                                                         
        b = r;                                                                                         
    } while (r != 0);                                                                                  
                                                                                                       
    printf("GDC: %d\n", a);                                                    
                                                                                                       
    return 0;            
}

출처 : 수학독본