Prime divided by 60

317 Views Asked by At

It has been proved on this website that the rest of a prime divided by $30$ will be either a prime or $1$, but can we get to the same conclusion if we divide a prime by multiples of $30$ (60,90,120...)?

Original question here.

(If a prime $p$ is divided by 30, remainder is either prime or 1)

2

There are 2 best solutions below

5
On BEST ANSWER

Modulo $60$ we have that $109$ (which is prime) is congruent to $49$, so no.

For any multiple $30n$ or $30$, there will always be primes which do not have prime remainders when divided by $30n$. Specifically, take any two (not necessarily distinct) primes $p, q$ (can also take more than two if you want) such that neither divides $30n$, and if $pq<30n$ then $pq$ is a composite remainder which is guaranteed to have primes in its congruency class. The thing with $30$ is that $30$ is too small for this to work, while for $60$ there is $p = q = 7$, and so on.

1
On

Given a positive composite modulo $m$ and a prime $p > m$, the remainder $r = p - mq$, with $q$ chosen so that $0 < r < m$, can be any number that is coprime to $m$ even if not itself prime.

Remember that 1 is coprime to all integers, including itself, even though they are all divisible by it. That way, $a$ and $b$ being coprime means $\gcd(a, b) = 1$.

So, with $m = 60$, and a prime $p > 59$, the possible $r$ are: 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59 (these are the first sixteen numbers listed in Sloane's A007775).

As you well know, 1 is not prime, and so any number $qm + 1$ is coprime to $m$ and thus potentially prime.

With $m = 30$, we see that 31 and 61 are indeed primes, while 91 and 121 are not. But take note of the fact that the least prime factor of 91 is 7, which is not a factor of 30, and likewise 121 is the square of 11, which is also not a factor of 30.

This should alert you to facts like that there are primes $p \equiv 91 \pmod{120}$ or $p \equiv 121 \pmod{240}$, such as 211 and 601, to give just a few examples.

The special thing about 30 is that it "is the largest number with the property that all smaller numbers relatively prime to it are prime" (except 1 of course), see Erick Friedman's "What's Special About This Number?"

Any $m > 30$ will give you at least one composite $r$. For 32 that would be 9, 15, 21, 25, 27, which correspond to primes like 41, 47, 53, 89, 59. For 60, like Arthur already said, that would be just 49.

You can have Wolfram Mathematica give you a list of $r$ with Select[Range[60], GCD[#, 60] == 1 &], I think this works in Wolfram Alpha as well. For other $m$, just change 60 in both spots, or declare a function that takes an argument m.