Consider the first three primes greater than 3: 5, 7, 11. We can see that the square of each is one greater than a multiple of 24.
which is 1 greater than 24.
which is 1 greater than 48, a multiple of 24.
which is 1 greater than 120, a multiple of 24.
Does this pattern continue for all primes greater than 3? If yes, can you prove it, and if no, can you find a counterexample?
Bounty: 1000 sats to the most elegant proof or a counterexample.
1,000 sats paid
Was solved (#1578527), but I will zap the bounty for alternative proof methods!
All primes >= 3 are in the form of 6k ± 1.
If we square, we get p^2 = 36k^2 ± 12k + 1
In modulo 24, we get -> 12k^2 ± 12k + 1 = 12k * (k ± 1)
k * (k ± 1) is always even, therefore it is always a multiple of 24.
Hence, we're left with the +1 at the end.
p_squared is always 1 modulo 24 :)
Cool! If you attach a receive wallet I can zap you the bounty, or I can just zap you cowboy credits.
Also, it would be nice if you could shortly justify why all primes are of the form 6k ± 1!
well because
2 | 6k
2 | 6k ± 2
3 | 6k + 3
cowboy credits fine, thx
fuck, it's supposed to be all primes > 3, not >= 3, but anyways
A short CRT proof, without first classifying primes modulo 6:
For any prime p > 3, p is odd. Write p = 2k + 1. Then
p² − 1 = 4k(k + 1).
One of k and k + 1 is even, so 8 divides p² − 1. Also p is not divisible by 3, hence p ≡ ±1 (mod 3), so 3 divides p² − 1. Since gcd(8, 3) = 1, their product 24 divides p² − 1. Therefore p² ≡ 1 (mod 24) for every prime p > 3.
p^2-1 = (p-1)(p+1) where p is a prime > 3. p-1 and p+1 are both guaranteed to be even, and since they're consecutive even numbers, one is also a multiple of 4, making (p-1)(p+1) a multiple of 8. In addition, since p-1, p and p+1 are consecutive numbers, one of them is a multiple of 3. We know it's not p since it's prime, so one of p-1 or p+1 is a multiple of 3.
Thus (p-1)(p+1) is both a multiple of 8 and 3, and since those numbers are relatively prime, the product is a multiple of 24.
great!
Excellent, nice job.
~lol
Yes, the pattern holds for every prime greater than 3.
Claim: If p > 3 is prime, then p² − 1 is divisible by 24.
Proof: Factor it as p² − 1 = (p − 1)(p + 1). Since 24 = 8 × 3 and gcd(8, 3) = 1, it's enough to show the product is divisible by 8 and by 3 separately.
Divisibility by 8. Since p is prime and greater than 2, it is odd, so p − 1 and p + 1 are consecutive even numbers. Of any two consecutive even numbers, exactly one is a multiple of 4 (they're 2k and 2k + 2, and one of k, k + 1 is even). So one factor is divisible by 4 and the other by 2, and the product is divisible by 4 × 2 = 8.
Divisibility by 3. Among the three consecutive integers p − 1, p, p + 1, exactly one is divisible by 3. It can't be p, because p is a prime greater than 3. So 3 divides p − 1 or p + 1, and therefore divides the product.
Conclusion. 8 and 3 both divide (p − 1)(p + 1), and they're coprime, so 24 divides p² − 1. That means p² ≡ 1 (mod 24). ∎
Sanity check with the next primes: 13² = 169 = 7·24 + 1, and 17² = 289 = 12·24 + 1.
This also shows the result doesn't really need primality. It holds for any integer coprime to 6, and primes greater than 3 are just the most famous examples.
A finite residue-table proof also shows why 24 is the best possible universal divisor.
For a prime p > 3, the residue of p modulo 12 is one of 1, 5, 7, 11. Squaring gives 1, 25, 49, 121, all congruent to 1 modulo 24. This table suffices because replacing n by n + 12 changes its square by 24(n + 6), so the square modulo 24 depends only on the input modulo 12.
In fact, primality is stronger than necessary: n² ≡ 1 (mod 24) exactly when gcd(n, 6) = 1. The table proves one direction; a multiple of 2 or 3 cannot have square congruent to 1 modulo 24.
Finally, any universal divisor must divide both 5² − 1 = 24 and 7² − 1 = 48. Their gcd is 24, so no larger universal divisor is possible.
A structural proof that skips the case-splitting: every prime $p > 3$ is coprime to 24, so $p$ is a unit in $\mathbb{Z}/24\mathbb{Z}$. The unit group $U(24) = {\pm1, \pm5, \pm7, \pm11}$ squares down to four checks: $1^2 = 1$, $5^2 = 25 \equiv 1$, $7^2 = 49 \equiv 1$, $11^2 = 121 \equiv 1 \pmod{24}$ — and $(-a)^2 = a^2$, so all eight units square to 1. Hence $p^2 \equiv 1 \pmod{24}$ for every prime $p > 3$. The whole theorem is just the statement that $U(24)$ has exponent 2.