Christmas Questions: No. 3

Notice that ${ x }^{ n }-1=(x-1)({ x }^{ n-1 }+{ x }^{ n-2 }{ +......+ x }+1)$

• If ${x-1}$ is a prime number, then we can conclude that ${ x }^{ n }-1$ can produce a prime if we set ${n=1}$ .

For example, ${ 74 }^{ n }-1=(74-1)(74^{ n-1 }+{ 74 }^{ n-2 }+......+74+1)$ $=(73)(74^{ n-1 }+{ 74 }^{ n-2 }+......+74+1)$

Since ${73}$ is a prime number, ${ 74 }^{ n }-1$ can produce a prime if we set ${n=1}$ .

• If ${x-1}$ is a composite number, then we can conclude that ${ x }^{ n }-1$ can never produce a prime for any ${n}$ because ${ x }^{ n }-1$ will have a factor of ${x-1}$ .

For example, ${ 75 }^{ n }-1=(75-1)(75^{ n-1 }+{ 75 }^{ n-2 }+......+75+1)$ $=(74)(75^{ n-1 }+{ 75 }^{ n-2 }+......+75+1)$

Since ${74}$ is not a prime number, ${{ 75 }^{ n }-1}$ can never produce a prime as it will always have a factor of 74.

Therefore, ${ x }^{ n }-1$ can produce a prime if ${x-1}$ is a prime. Since there are 25 primes under 100, we can produce those primes in the form of $(p+1)^{ n }-1$ , where ${p}$ is a prime number.

We also cannot ignore the number ${2}$ as $2^{ n }-1$ can also produce some primes, otherwise known as [Mersenne Primes], (https://en.wikipedia.org/wiki/Mersenne_prime).

Therefore, we have ${25}$ prime numbers and the number ${2}$ that can be produced or produce primes in the form $x^{ n }-1$ .

That means that $100-26=\boxed{74}$ integers cannot produce prime numbers.