Dividing any prime number by 30 always results in a remainder that is either prime or equal to 1.
Why?

Show that it does not work when 60 replaces 30.

The remainder after division by 30 will always be lower than 30.

Any composite number will have some prime factor less than or equal to its square root, so a composite number lower than 30 will have a prime factor lower than sqrt(30), and so must be 2, 3 or 5.

But any remainder after dividing by 30 that has one of these factors requires that the original number being divided be divisible by one of these factors, as the quotient portion after the division is divisible by each of these, as 30=2*3*5. So only in the case of a composite original number will the remainder after division be composite.

In the case given, the original number will be prime, so the given remainder cannot be composite, and must be either prime or 1.

In the case of division by 60, in the above step where there must be a factor below the square root, that's sqrt(60), and so 7 is allowed as a prime factor.

The below prime numbers all leave a remainder of 49 when divided by 60:

109
229
349
409
709
769
829
1009
1069
1129
1249
1429
1489
1549
1609
1669
1789
2029
2089

and 49 is obviously composite at 7*7.

Posted by Charlie on 2012-12-03 12:05:16