# Divisibility test using perhaps binomial thorem

I have to determine if $17^{21} + 19^{21}$ is divisible by any of the following numbers (a) 36 (b) 19 (c) 17 (d) 21. I am trying to find using binomial expansion but getting stuck up with one or two terms - being not able to determine the divisibility. Any help will be highly appreciated.

• For the first, note that if $n$ is odd then $x+y$ divides $x^n+y^n$. – André Nicolas Sep 26 '15 at 23:42
• @Andre! that is great! That fits the answer given in my book. what is the proof of your statement for every odd n. I can think of mathematical inductional proof! Is there any other type of proof? Thanks once again! – Seetha Rama Raju Sanapala Sep 27 '15 at 1:44

First problem: There are many approaches. Since you mentioned the Binomial Theorem, let us first do it that way. We have $$17^{21}=(18-1)^{21}=18^{21}-\binom{21}{1}18^{20}+\binom{21}{2}18^{19}-\binom{18}{3}18^{18}+\cdots -\binom{21}{21}18^0.$$ Similarly, $$19^{21}=(18+1)^{21}=18^{21}+\binom{21}{1}18^{20}+\binom{21}{2}18^{19}+\binom{18}{3}18^{18}+\cdots +\binom{21}{21}18^0.$$ Add, and observe the cancellations. Each term that remains is divisible by $2\cdot 18$.

Another way to do it is to use the fact that for odd $n$ we have $$x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+x^{n-3}y^2-\cdots +y^n.$$ A particular case if this identity may be familiar to you: $x^3+y^3=(x+y)(x^2-xy+y^2)$.

Take $x=17$, $y=19$, and $n=21$. We get that $17^{21}+19^{21}$ is equal to $(17+19$ times a complicated expression. We don't need to evaluate the expression to see that it is an integer.

Still another way to do it is to use congruences. We have $19\equiv -17\pmod{36}$. Thus $$17^{21}+19^{21}\equiv 17^{21}+(-17)^{21}\equiv 17^{21}-17^{21}\equiv 0\pmod{36}.$$

Remark: The next two problems are not difficult. The last one is harder. The right tools to use depend on what number-theoretic tools are already available to you.

Added: The second and third problems are nearly identical. Suppose that $19$ divides $17^{21}+19^{21}$. Since $19$ divides $19^{21}$, it follows that $19$ divides $17^{21}$. But if a prime divides a product, it divides at least one of the terms. So we conclude that $19$ divides $17$, which is false. It follows that $19$ cannot divide $17^{21}+19^{21}$.

For the last problem, we will show that $7$ does not divide our sum. It follows that $21$ cannot. We work modulo $7$.

By Fermat's Theorem we have $17^6\equiv 1\pmod{7}$. So $17^{18}\equiv 1\pmod{7}$ and therefore $17^{21}\equiv 17^3\equiv 3^3\pmod{7}$.

Similarly, $19^{21}\equiv 5^3\pmod{7}$. But $3^3+5^3=152\not\equiv 0\pmod{7}$.

• You are right. You make things so simple! I don't see 'accept answer' option/item. How do I accept the answer? Can you also throw light on the divisibility by 17, 19 and 21? – Seetha Rama Raju Sanapala Sep 27 '15 at 3:17
• I don't know about the accept process, have not yet asked a question. It cannot be hard, lots of people do it. As to the Question d) it would be useful, as I indicated, to know what tools you have. Congruences? Fermat "little" Theorem? Euler's Theorem and the Euler $\varphi$-function? For Questions b) and c) all you need is the fact that if a prime divides a product then it divides one of the terms. If you give some indication of your number theoretic knowledge, I can try to give an answer that is appropriate. – André Nicolas Sep 27 '15 at 3:29
• May be some minimum reputation required to accept answers! I have accepted answers on the other stackexchanges. I know number theory. I know Chinese remiander theorem, congruences, Fermat's last theorem etc. – Seetha Rama Raju Sanapala Sep 27 '15 at 4:05