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$ .