Can anybody help me with this problem?
Prove that for every integer $n$, $$p(n) = n^{18} - n^{14} - n^6 + n^2$$ is divisible by $65$.
Thanks!
Asked
Active
Viewed 70 times
-2
PM 2Ring
- 4,844
-
What's the source of this problem? – Magma Nov 26 '20 at 17:24
-
Yes I got to that point. But I cannot factorize the equation so that I could prove that I can divide it by 5 or 13 – Aleksandre Bregadze Nov 26 '20 at 17:24
-
Please edit your question to include the source of this problem. – Magma Nov 26 '20 at 17:26
-
source? You mean book? – Aleksandre Bregadze Nov 26 '20 at 17:27
-
Presumably, you would be given this assignment if you are already familiar with Fermat's little theorem, and (probably) Euler's theorem. – PM 2Ring Nov 26 '20 at 17:27
-
yes both but the issue I am facing is that I cannot get the n^x == n(modx)... I need to somehow factorize the equation but I am not getting how – Aleksandre Bregadze Nov 26 '20 at 17:29
-
Euler's isn't actually helpful here, since $\phi(65)=48$, but all our exponents are <48. But as the answers below show, we can attack it with little Fermat & the CRT. – PM 2Ring Nov 26 '20 at 17:39
2 Answers
3
Hints:
Factor it as $n^2(n^{4}-1)(n^{12}-1)=(n^5-n)(n^{13}-n)$.
Note that $65=5\times13$.
Now use Fermat's little theorem.
J. W. Tanner
- 60,406
-
1
-
1Actually, you can easily use Fermat's little theorem on $$n^2(n^{16}-n^{12}-n^4+1)$$ You don't need to factorise it any further. – PM 2Ring Nov 26 '20 at 17:36
-
1I used the first form and used theorem on non prime powers – Aleksandre Bregadze Nov 26 '20 at 17:37
0
Hint:
Use lil' Fermat and the Chinese remainder theorem:
- Modulo $5$, we have $n^5\equiv n$ for all $n$, hence $$n^{18}=n^{15}n^3=(n^5 n)^3\equiv (n^2)^3=n^6\equiv n^2 \\ n^{14}=n^{10}n^4=(n^5n^2)^2\equiv(n^3)^2=n^6\equiv n^2\\ \text{so that }\quad n^{18} - n^{14} - n^6 + n^2\equiv n^2-n^2-n^2+n^2=0 \mod 5.$$
- Similarly, modulo $13$, we have $n^{13}\equiv n$ for all $n$. Can you proceed?
J. W. Tanner
- 60,406
Bernard
- 175,478