# Number theory primes and congruences: $p^{32} -1$ is divisible by $16320$

I had problem in the following problem any help or hint will highly be appreciated.

For $p>17$, $p^{32} -1$ is divisible by $16320$

• Welcome user 253752 – Piquito Nov 23 '15 at 11:48
• A relevant link to the OEIS: oeis.org/A079612. In fact $p^{32}-1$ is divisible by 16320 whenever $p$ has no factors in common with $16320$. – Michael Lugo Nov 23 '15 at 14:42
• – lab bhattacharjee Nov 25 '15 at 15:52

Hint: we have $16320=2^6\cdot 3\cdot 5\cdot 17$, and already $p^{32}\equiv 1 \bmod k$ for each $k\in \{2^6,3,5,17\}$. For example, $p^2\equiv 1\bmod 3$, because $\gcd(p,3)=1$.

You have $16320=2^6\cdot3\cdot5\cdot17$.

Notice that using Fermat's theorem you have:

• $p^{16}\equiv1\pmod{17}$, hence also $p^{32}=(p^{16})^2\equiv1\pmod{17}$
• $p^4\equiv1\pmod5$, hence also $p^{32} \equiv 1 \pmod5$
• $p^2\equiv1\pmod3$. hence also $p^{32} \equiv 1\pmod3$

Now it only remains to notice that $\phi(64)=32$ and by Euler's theorem $p^{32}\equiv1\pmod{64}$.

And now you can combine the above congruences together.

• Thanks for correcting the typo/mistake in my post @Barry Cipra. – Martin Sleziak Nov 23 '15 at 15:54

Note that:

• $p^{32}-1=(p-1)(p+1)(p^{2}+1)(p^{4}+1)(p^{8}+1)(p^{16}+1)$
• $p>5\text{ is prime} \implies p\equiv1,7,11,13,17,19,23,29\pmod{30}$

$p\equiv1\pmod{30}\implies$

• $p -1\equiv1 -1\equiv0\pmod{30}\implies30\mid{p -1}$
• $p +1\equiv1 +1\equiv2\pmod{30}\implies 2\mid{p +1}$
• $p^{ 2}+1\equiv1^{ 2}+1\equiv2\pmod{30}\implies 2\mid{p^{ 2}+1}$
• $p^{ 4}+1\equiv1^{ 4}+1\equiv2\pmod{30}\implies 2\mid{p^{ 4}+1}$
• $p^{ 8}+1\equiv1^{ 8}+1\equiv2\pmod{30}\implies 2\mid{p^{ 8}+1}$
• $p^{16}+1\equiv1^{16}+1\equiv2\pmod{30}\implies 2\mid{p^{16}+1}$

$\implies30\cdot2\cdot2\cdot2\cdot2\cdot2=\color\red{960}\mid{p^{32}-1}$

$p\equiv7\pmod{30}\implies$

• $p -1\equiv7 -1\equiv 6\pmod{30}\implies 6\mid{p -1}$
• $p +1\equiv7 +1\equiv 8\pmod{30}\implies 2\mid{p +1}$
• $p^{ 2}+1\equiv7^{ 2}+1\equiv20\pmod{30}\implies10\mid{p^{ 2}+1}$
• $p^{ 4}+1\equiv7^{ 4}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 4}+1}$
• $p^{ 8}+1\equiv7^{ 8}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 8}+1}$
• $p^{16}+1\equiv7^{16}+1\equiv 2\pmod{30}\implies 2\mid{p^{16}+1}$

$\implies6\cdot2\cdot10\cdot2\cdot2\cdot2=\color\red{960}\mid{p^{32}-1}$

$p\equiv11\pmod{30}\implies$

• $p -1\equiv11 -1\equiv10\pmod{30}\implies10\mid{p -1}$
• $p +1\equiv11 +1\equiv12\pmod{30}\implies 6\mid{p +1}$
• $p^{ 2}+1\equiv11^{ 2}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 2}+1}$
• $p^{ 4}+1\equiv11^{ 4}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 4}+1}$
• $p^{ 8}+1\equiv11^{ 8}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 8}+1}$
• $p^{16}+1\equiv11^{16}+1\equiv 2\pmod{30}\implies 2\mid{p^{16}+1}$

$\implies10\cdot6\cdot2\cdot2\cdot2\cdot2=\color\red{960}\mid{p^{32}-1}$

$p\equiv13\pmod{30}\implies$

• $p -1\equiv13 -1\equiv12\pmod{30}\implies 6\mid{p -1}$
• $p +1\equiv13 +1\equiv14\pmod{30}\implies 2\mid{p +1}$
• $p^{ 2}+1\equiv13^{ 2}+1\equiv20\pmod{30}\implies10\mid{p^{ 2}+1}$
• $p^{ 4}+1\equiv13^{ 4}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 4}+1}$
• $p^{ 8}+1\equiv13^{ 8}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 8}+1}$
• $p^{16}+1\equiv13^{16}+1\equiv 2\pmod{30}\implies 2\mid{p^{16}+1}$

$\implies6\cdot2\cdot10\cdot2\cdot2\cdot2=\color\red{960}\mid{p^{32}-1}$

$p\equiv17\pmod{30}\implies$

• $p -1\equiv17 -1\equiv16\pmod{30}\implies 2\mid{p -1}$
• $p +1\equiv17 +1\equiv18\pmod{30}\implies 6\mid{p +1}$
• $p^{ 2}+1\equiv17^{ 2}+1\equiv20\pmod{30}\implies10\mid{p^{ 2}+1}$
• $p^{ 4}+1\equiv17^{ 4}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 4}+1}$
• $p^{ 8}+1\equiv17^{ 8}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 8}+1}$
• $p^{16}+1\equiv17^{16}+1\equiv 2\pmod{30}\implies 2\mid{p^{16}+1}$

$\implies2\cdot6\cdot10\cdot2\cdot2\cdot2=\color\red{960}\mid{p^{32}-1}$

$p\equiv19\pmod{30}\implies$

• $p -1\equiv19 -1\equiv18\pmod{30}\implies 6\mid{p -1}$
• $p +1\equiv19 +1\equiv20\pmod{30}\implies10\mid{p +1}$
• $p^{ 2}+1\equiv19^{ 2}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 2}+1}$
• $p^{ 4}+1\equiv19^{ 4}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 4}+1}$
• $p^{ 8}+1\equiv19^{ 8}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 8}+1}$
• $p^{16}+1\equiv19^{16}+1\equiv 2\pmod{30}\implies 2\mid{p^{16}+1}$

$\implies6\cdot10\cdot2\cdot2\cdot2\cdot2=\color\red{960}\mid{p^{32}-1}$

$p\equiv23\pmod{30}\implies$

• $p -1\equiv23 -1\equiv22\pmod{30}\implies 2\mid{p -1}$
• $p +1\equiv23 +1\equiv24\pmod{30}\implies 6\mid{p +1}$
• $p^{ 2}+1\equiv23^{ 2}+1\equiv20\pmod{30}\implies10\mid{p^{ 2}+1}$
• $p^{ 4}+1\equiv23^{ 4}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 4}+1}$
• $p^{ 8}+1\equiv23^{ 8}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 8}+1}$
• $p^{16}+1\equiv23^{16}+1\equiv 2\pmod{30}\implies 2\mid{p^{16}+1}$

$\implies2\cdot6\cdot10\cdot2\cdot2\cdot2=\color\red{960}\mid{p^{32}-1}$

$p\equiv29\pmod{30}\implies$

• $p -1\equiv29 -1\equiv28\pmod{30}\implies 2\mid{p -1}$
• $p +1\equiv29 +1\equiv 0\pmod{30}\implies30\mid{p +1}$
• $p^{ 2}+1\equiv29^{ 2}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 2}+1}$
• $p^{ 4}+1\equiv29^{ 4}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 4}+1}$
• $p^{ 8}+1\equiv29^{ 8}+1\equiv 2\pmod{30}\implies 2\mid{p^{ 8}+1}$
• $p^{16}+1\equiv29^{16}+1\equiv 2\pmod{30}\implies 2\mid{p^{16}+1}$

$\implies2\cdot30\cdot2\cdot2\cdot2\cdot2=\color\red{960}\mid{p^{32}-1}$

• @Mathslovershah: You're welcome :) – barak manos Nov 24 '15 at 5:57

NOTE. It would be absurd that this property is valid for all prime number greater than $17$; indeed $29^{32}-1=(29^{16}-1)(29^{16}+1)$. Calculating we have $29^{16}=250246473680347348787 521$ and it is verify that neither $29^{16}-1$ nor $29^{16}+1$ is divisible by $17$ hence not divisible by a multiple of $17$ thus not divisible by 16320.

NOTE (bis).The first note was a mistake induced by both, certain idea about the anarchy of primes and the calculator. It is so clear that the property of divisibility by $17$ is true……. The "hidden" $16 = 17-1$, which could be applied to any prime p with the exponent appropriate $2(p-1)$..... But this usually happens. See for example my answer to "Can a pre-calculus student prove this?" and compare it with the other ones. Here also the answer is immediate but qualified people did not see.

Therefore the question must be understand as looking for a prime satisfying the enunciated property. I find below the prime $p=16319$

The number $p=16320-1=16319$ is prime and $p^{32}=16320M+1$ for some $M$. Hence you have $p^{32}-1$ is a multiple of $16320$.

Note anyway that for all even k you have the same result.

• Either I didn't understand the question, or I didn't understand your answer. Where exactly does the question say that $p=16320-1$??? – barak manos Nov 23 '15 at 11:57
• I think the question was deficiently formulated by user 253752. On the other hand it would be absurd that the rule be true for all prime > 17 therefore it was looking for a particular prime. I gave one, the prime 16319. – Piquito Nov 23 '15 at 12:03
• What makes you think that it would be absurd for all primes $>17$? It can easily be proved that $192$ divides $p^{32}-1$ for all primes $>17$. Personally, I've managed to prove it even further, with $960$. What makes you think that it is wrong with $16320$??? (unless you have a counterexample of course). – barak manos Nov 23 '15 at 12:05
• If that is true then the number 17 deserves a monument: he is able to emulate the exploits of abusive 2,3 and 5. – Piquito Nov 23 '15 at 12:17
• 14720380804726314634560*17=250246473680347348787520=29^16-1 – jcsahnwaldt says GoFundMonica Nov 23 '15 at 14:59