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
is a multiple of 24.
Solution
=
=
=
.
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
.
Solution
=
=
=
=
.
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.
QED. Proved and solved.
Problem 6
Prove that
is divisible by 5 for any natural n.
Solution
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.
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