Lesson Introductory problems on divisibility of integer numbers

Introductory problems on divisibility of integer numbers

Problem 1

a)  If n divides 3 then the statement is proved.

    If n does not divide 3 without a remainder, then the remainder is either 1 or 2.


    b)  If the remainder is 1, then 2n+1 has the remainder 2*1+1 = 3;
        in other words, then 2n +1 is a multiple of 3.


    c)  If the remainder is 2, then n+1 is divisible by 3.


Thus, in all cases one of the three numbers n, n+1 or 2n+1 is divisible by 3.

Problem 2

a)  If n divides 3 then the statement is proved.

    If n does not divide 3 without a remainder, then the remainder is either 1 or 2.


    b)  If the remainder is 1, then n+2 is divisible by 3.


    c)  If the remainder is 2, then n+4 is divisible by 3.


Thus, in all cases one of the three numbers n, n+2 or n+4 is divisible by 3.

Problem 3

Problem 4

 =  =  = .


You have a product of three consecutive integers. 


One of them is a multiple of 3.


If n is odd, then both (n-1) and (n+1) are even, i.e. are multiples of 2.


Moreover, one of these two is a multiple of 4.


Therefore, the entire product is a multiple of 2*3*4 = 24.

Problem 5

 =  =  =  = .


If n is a multiple of 5, the statement is true.


If n gives the remainder 1 when divided by 5, then the factor (n-1) is a multiple of 5, and the statement is true.


If n gives the remainder 4 when divided by 5, then the factor (n+1) is a multiple of 5, and the statement is true.


If n gives the remainder 2 when divided by 5, then the factor (n^2+1) is a multiple of 5. 
     Indeed, the remainder of division by 5 is  = 5 (equivalent to 0) in this case, and the statement is true.


If n gives the remainder 3 when divided by 5, then the factor (n^2+1) is a multiple of 5. 
     Indeed, the remainder of division by 5 is  = 10 (equivalent to 0) in this case, and the statement is true.


Thus the statement is true in all cases.

Problem 6

Let us factor  as far as we can:


 =  =  = 


Now, if n is a multiple of 5, then    is a multiple of 5.


If n gives a remainder 1 when divided by 5, then the factor (n-1) is a multiple of 5.


If n gives a remainder 4 when divided by 5, then the factor  (n+1)  is a multiple of 5.


If n gives a remainder 2 or 3 when divided by 5, then the factor   is a multiple of 5.


So, in any case    is a multiple of 5,  and the statement is proved.

Problem 7

Let's assume that  (2n+1)  is a divisor of  N = 8n+46.


Notice that that  (2n+1)  is a divisor of the number  M = 8n+4  (simply because  8n+4 = 4*(2n+1) ).


It implies that the difference  N-M  is a multiple of  (2n+1), too.


But the difference  N-M  is equal to  (8n+46) - (8n+4) = 46-4 = 42.


Thus the number (2n+1) is a divisor of the number 42.


We can list all the ODD divisors of the number 42.


They are  3, 7 and 21, giving these equations to determine n


    2n+1 = 3;   2n+1 = 7   and  2n+1 = 21.


These equations have the following solutions, respectively


    n = 1;       n = 3     and    n = 10.


So, we solved the problem and found out all opportunities for n  as  1, 3  and 10.      ANSWER

Problem 8

All these six-digit numbers, described in the post, are of the form

      N = 1000n + n = 1001n,

where n is a/(any) three digit number.


Therefore, all such 6-digit numbers have common factor  1001, and this number 1001 is their Greatest Common Divisor.


The prime decomposition of number  1001  is  1001 = 7*11*13.


Its positive prime factors are  7, 11, 13.


The sum of these factors is 7 + 11 + 13 = 31.


ANSWER.  31.