# Solutions: More practice problems on Divisibility for RMO

Problem 1) Show that the number $1^{47} + 2^{47} + 3^{47} + 4^{47} + 5^{47} + 6^{47}$ is a multiple of 7.

Answer 1) If n is an odd positive integer, we know that $a+b|a^{n}+b^{n}$. Therefore, $7= 1 + 6|1^{47}+6^{47}$, $2+5|2^{47}+5^{47}$, $7=3+4|3^{47}+4^{47}$ and the result follows.

Problem 2) Compute the value of the expression $\frac{(10^{4}+324)(22^{4}+324)(34^{4}+324)(46^{4}+324)(58^{4}+324)}{(4^{4}+324)(16^{4}+324)(28^{4}+324)(40^{4}+324)(52^{4}+324)}$.

Answer 2) (American Invitational Mathematics Examination) Let N be the number to compute. Since $324 = 18^{2}$ and since $a^{4}+18^{2} = (a^{2}+18)^{2}-36a^{2} = (a^{2}+18+6a)(a^{2}+18-6a)$, then the number N can be written as

$N = \prod_{k=0}^{4}\frac{(10+12k)^{4}+18^{2}}{(4+12k)^{4}+18^{2}}$

$N = \prod_{k=0}^{4}\frac{[(10+12k)^{2}+18+6(10+12k)][(10+12k)^{2}+18-6(10+2k)]}{[(4+12k)^{2}+18+6(4+12k)][(4+12k)^{2}+18-6(4+12k)]}$

$N = \prod_{k=0}^{4}\frac{(144k^{2}+312k+178)(144k^{2}+168k+58)}{(144k^{2}+168k+58)(144k^{2}+24k+10)}$

$N=\prod_{k=0}^{4}\frac{144k^{2}+312k+178}{144k^{2}+24k+10}$

But, since $144(k+1)^{2}+24(k+1)+10 = 144k^{2}+312k+178$, the number N can be written as

$N = \frac{144.4^{2}+312.4+178}{10}=373$.

Problem 3) Given $s+1$ integers $a_{0}, a_{1}, a_{2}\ldots a_{s}$ and a prime number p, show that p divides the integer

$N(n) = a_{0} + a_{1}n + a_{2}n^{2}+ \ldots + a_{s-1}n^{s-1}+a_{s}n^{s}$

if and only if p divides $N(r)$, for an integer r, $0 \leq r \leq p-1$. Use this to find all integers n such that 7 divides $3n^{2}+6n+5$.

Answer 3) Let $n = kp+r$, $0 \leq r \leq p-1$. Using the binomial theorem, we obtain

$N(n) = a_{0} + a_{1}(kp+r) + \ldots + a_{s-1}(kp+r)^{s-1}+ a_{s}(kp+r)^{n}$

$N(n) = N(r) + pM$

for a certain integer M. Hence, $p|N(n)$ if and only if $p|N(r)$.

Setting $n = 7k+r$, $0 \leq r \leq 6$, we find that the required integers are those of the form $n=7k+1$ as well as those of the form $n=7k+4$.

Problem 4) Show that there exist infinitely many pairs of integers $\{ x, y\}$ satisfying $x + y = 40$ and $(x, y) = 5$.

Solution 4:

Let a and b be two arbitrary integers, and put $x = 5a$, and $y =5b$. In order to have $x+y = 5a+5b=40$, we must have $a+b=8$. Moreover, to have $(x, y) =5$, we must have $(a, b) = 1$. Therefore, it remains to show that it is possible to find infinitely many relatively prime pairs of integers a and b such that $a + b= 8$. To do so, it is enough to choose, for example, $a = 3 +2t$ and $b = 5-2t$, where $t \in Z$.

Problem 5) Prove that one cannot find integers m and n such that $m + n = 101$ and $(m, n) = 3$.

Solution 5:

This follows from the fact that $3|m$ and $3|n$, while 3 does not divide 101.

More later,

Nalin Pithwa

This site uses Akismet to reduce spam. Learn how your comment data is processed.