11 ms·
I tried coming up with a proof, but instead I have a new observation I can't explain: FACT: No prime number can end in an even number (because all such numbers
by sbandyopadhyay 14y ago
I tried coming up with a proof, but instead I have a new observation I can't explain:
FACT: No prime number can end in an even number (because all such numbers are divisible by 2) or in 5 (because all such numbers are divisible by 5). So, all prime numbers must end in: 1, 3, 7, or 9.
FACT: When you multiply 2 numbers, the units digit of the product is the same as the units digit of the product of the units digits of the two numbers.
FACT: Combining the last two facts, every prime number squared must end in 1 (if the prime ended in 1 or 9) or 9 (if the prime ended in 3 or 7).
FACT: Thus, every prime square modulo 40 must be one of the following numbers (and cannot be any other number): 1, 9, 11, 19, 21, 29, 31, or 39.
So, I just have to figure out now why 6 of those 8 numbers can't be prime squares modulo 40. That's when I noticed something odd: no number x, such that x modulo 40 is 11, 19, 21, 29, 31, or 39, is a perfect square. (Tried this through x = 1 million.)
Anyone know why that is?
- alexkus 14y agohttps://en.wikipedia.org/wiki/Quadratic_residue https://en.wikipedia.org/wiki/Quadratic_residue also the Legendre symbol. Also there's no need to consider numbers >= 40 when working mod 40 47 * 47 (mod 40) = (40+7) * (40+7) (mod 40) 40 * n = 0 (mod 40) for any integer n since 40*n will be a multiple of 40, so:- = 40*(40+7) + 7*(40+7) (mod 40) = 0 + 7*(40+7) (mod 40) = 7 * (40+7) (mod 40) = 7*7 + 7*40 (mod 40) = 7*7 + 0 (mod 40) = 7*7 So n^2 (mod 40) = (n mod 40)^2 (mod 40).