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)}


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







Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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