1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For the first, note that if $n$ is odd then $x+y$ divides $x^n+y^n$. $\endgroup$ – André Nicolas Sep 26 '15 at 23:42
  • $\begingroup$ @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! $\endgroup$ – Seetha Rama Raju Sanapala Sep 27 '15 at 1:44
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Seetha Rama Raju Sanapala Sep 27 '15 at 3:17
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Sep 27 '15 at 3:29
  • $\begingroup$ 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. $\endgroup$ – Seetha Rama Raju Sanapala Sep 27 '15 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.