Prime Number Diagrams in Python and SVG(alphapixel.com) |
Prime Number Diagrams in Python and SVG(alphapixel.com) |
As the author observes, if x and m share a common divisor, then there can be at most one prime congruent x modulo m [3]. The interesting classes are those with gcd(x,m) = 1. For those Dirichlet's Theorem on primes in arithmetic progressions [1] tells us that we will in fact find infinitely many primes in these residue classes. More refined, the prime number theorem for arithmetic progressions [2] tells us something about their distribution.
As for the squares of primes: If m = 40 then the residue classes modulo m which will contain infinitely many primes can be represented by:
1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37
Therefore the only residue classes in which infinitely many square of primes can lie are the squares of these residue classes, which turn out to be represented by 1 and 9 modulo 40 (just square the previous numbers and take remainders of dividing by 40).
This explains why all but finitely many of the squares of primes lie in the two rays corresponding to these residue classes.
[1] https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arith...
[2] https://en.wikipedia.org/wiki/Prime_number_theorem#Prime_num...
[3] Suppose d = gcd(x,m). If y is congruent x mod m, then m divides y-x. Since d therefore divides x and y-x, it divides y. If d is not 1, then y can only be a prime if y=d and d is a prime.
(one more edit): We can also say which classes will contain a single prime and which ones will contain a unique prime square: If p is a prime that has a common divisor with m, then p mod m will contain a single prime (p itself). Then p^2 mod m will contain a single prime square (well, p^2). In the case m=40, we have that 2 and 5 are the prime divisors of 40. Therefore the residue classes represented by 2 and 5 contain a single prime, and those represented by 4 and 25 contain a single prime square.
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?
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).http://webcache.googleusercontent.com/search?q=cache%3Ahttp%...
All odd numbers have a p^2 mod 40 value that is 1, 9 or 25.
The margin isn't big enough for my proof, but only odd numbers with a multiple of 5 will have a p^2 mod 40 value that is 25. Once you remove the case for p=5 (by ignoring the 'inner ring' of numbers where p^2 < 40) then the only valid residues for odd numbers (that aren't multiples of 5) are 1 or 9, but, more importantly this is true whether they are prime or not.