Lesson Introductory problems on divisibility of integer numbers

Algebra ->  Divisibility and Prime Numbers -> Lesson Introductory problems on divisibility of integer numbers      Log On


   


This Lesson (Introductory problems on divisibility of integer numbers) was created by by ikleyn(52780) About Me : View Source, Show
About ikleyn:

Introductory problems on divisibility of integer numbers


Problem 1

For any integer  n,  prove that  3  divides one of the integers  n,  n + 1  or  2n + 1.

Solution

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.

QED.   Proved and solved.


Problem 2

For any integer  n,  prove that  3  divides one of  n,  n + 2  or  n + 4.

Solution

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.

QED.   Proved and solved.


Problem 3

For any integer  n,  prove that  3  divides one of  n,  2n - 1  or  2n +1.

Solution


Problem 4

Show that if  n  is an odd integer,  then  n%5E3-n  is a multiple of  24.

Solution

n%5E3+-+n = n%2A%28n%5E2-1%29 = n%2A%28n-1%29%2A%28n%2B1%29 = %28n-1%29%2An%2A%28n%2B1%29.


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.

QED.   Proved and solved.


Problem 5

Prove that for any integer  n,  5  divides  n%5E5-n.

Solution

n%5E5+-+n = n%2A%28n%5E4-1%29 = n%2A%28n%5E2-1%29%2A%28n%5E2%2B1%29 = n%2A%28n-1%29%2A%28n%2B1%29%2A%28n%5E2%2B1%29 = %28n-1%29%2An%2A%28n%2B1%29%2A%28n%5E2%2B1%29.


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 2%5E2%2B1 = 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 3%5E2%2B1 = 10 (equivalent to 0) in this case, and the statement is true.


Thus the statement is true in all cases.

QED.   Proved and solved.


Problem 6

Prove that  n%5E8+-+n%5E4  is divisible by  5  for any natural  n.

Solution

Let us factor n%5E8+-+n%5E4 as far as we can:


n%5E8+-+n%5E4 = n%5E4%2A%28n%5E4-1%29 = n%5E4%2A%28n%5E2%2B1%29%2A%28n%5E2-1%29 = n%5E4%2A%28n%5E2%2B1%29%2A%28n%2B1%29%2A%28n-1%29


Now, if n is a multiple of 5, then  n%5E8+-+n%5E4  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 %28n%5E2%2B1%29  is a multiple of 5.


So, in any case  n%5E8+-+n%5E4  is a multiple of 5,  and the statement is proved.

QED.   Proved and solved.


Problem 7

How many positive integers  " n "  are there such that  2n+1  is a divisor of  8n+46 ?

Solution

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

A six-digit number is formed by repeating a three-digit number as in  639639.
Find the sum of the prime factors all such numbers have in common.

Solution

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.


My other lessons in this site on miscellaneous problems on divisibility of integer numbers are
    - Light flashes on a Christmas tree and a Least Common Multiple
    - The number that leaves a remainder 1 when divided by 2, by 3, by 4, by 5 and so on until 9
    - The number which gives remainder 4 when divided by 7, remainder 5 when divided by 8 and remainder 6 when divided by 9
    - Finding Greatest Common Divisor of integer numbers
    - Relatively prime numbers help to solve problems
    - Solving equations in integer numbers
    - Quadratic polynomial with odd integer coefficients can not have a rational root
    - Proving an equation has no integer solutions
    - Composite number of the form (4n+3) must have a prime divisor of the form (4n+3)
    - Problems on divisors of a given number
    - How many three-digit numbers are multiples of both 5 and 7?
    - How many 3-digit numbers are not divisible by 2; not divisible by 3; not divisible by either 2 or 3
    - How many integer numbers in the range 1-300 are divisible by at least one of the integers 4, 6 and 15 ?
    - Find the remainder of division
    - Why 3^n + 7^n - 2 is divisible by 8 for all positive integer n ?
    - What is the last digit of the number a^n ?
    - Find the last three digits of these numbers
    - Find the last two digits of the number 3^123 + 7^123 + 9^123
    - Find the last two digits of (1! + 2! + 3! + ... + 2024!)^2024
    - Find n-th term of a sequence
    - Solving Diophantine equations
    - How many integers of the form n^2 + 18n + 13 are perfect squares
    - Miscellaneous problems on divisibility numbers
    - Find the sum of digits of integer numbers
    - Two-digit numbers with digit "9"
    - Find a triangle with integer side lengths and integer area
    - Math circle level problem on the hundred-handed monster Briareus
    - Math Circle level problem on lockers and divisors of integer numbers
    - Nice entertainment problems related to divisibility property
    - Solving problems on modular arithmetic
    - Using the little Fermat's theorem to solve a problem on modular arithmetic
    - OVERVIEW of miscellaneous solved problems on divisibility of integer numbers


This lesson has been accessed 2458 times.