Divisibility test using perhaps binomial thorem

Question

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.

Answer 1

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