My relatives are primes

Number Theory Level 5

What is the largest integer $N$ such that all the integers between $1$ and $N$ (Excluding $1$ and $N$ ) that are relatively prime to $N$ are primes?

The answer is 30.

1 solution

Steven Perkins
Apr 11, 2014

Call the number we are looking for N. In order not be relatively prime to 4, 8, 16... N should be a multiple of 2. In order to not be relatively prime to 9, 81, ... N should be a multiple of 3.

Continuing this way, we'd like N to be a multiple of 5. We're now up to 2 * 3 * 5 = 30 (or multiples of 30). Can we add 7 to the product? That gives us 210? Oops, now we've got 11 * 11 = 121 which is relatively prime to 230, but is NOT prime itself.

Can we use 60? No, because 7 * 7 = 49 is NOT prime. So the best we can do seems to be $\boxed{30}$

Basically it's $\prod_1^np_k<p_{n+1}^2$

Kenny Lau - 6 years, 11 months ago

My relatives are primes

The answer is 30.

1 solution

0 pending reports