Arithmetic+ 05: UNIZOR.COM - Math+ & Problems - Arithmetic

Notes to a video lecture on http://www.unizor.com

Arithmetic+ 05

Problem A
Prove that a remainder of division of any prime number P by 24 is a prime number, assuming P is greater than 24.

Hint A
If P is prime and R is a remainder of division of P by 24 then P=24·n+R where R≤23.
If R is not prime, it should be divisible by a product of, at least, two prime numbers.
Also, 24=2·2·2·3.


Problem B
Prove that for any natural number N the number 10^N+18·N−1 is divisible by 27.

Hint B
First, prove a theorem that any natural number n divided by 3 (or 9) has the same remainder as a sum of its digits divided by 3 (or 9).
Obviously, the given number is divisible by 9.
Then prove that the number 111...111 consisting of N unit digits with their sum equal to N plus 2·N is divisible by 3 using a theorem proved above.


Problem C
Prove that from any set of 100 natural numbers N₁, N₂,... ,N₁₀₀ it is possible to choose such a subset with a sum of its numbers divisible by 100.

Hint C
Let S_k=Σ_i∈[1,k]N_i
where k=1, 2,...,100.
If there is one particular number S_k divisible by 100, the components of this sum can be chosen as a subgroup and the problem is solved.
Assume, none of our 100 sums S_k is divisible by 100.
Let R_k is a remainder of division of S_k by 100.
Note that there are 99 possible remainders from 1 to 99.