Prime Number Puzzles

This page has a few puzzles involving prime numbers:

1. How many of the three digit numbers that can be made from all of the the digits 1, 3 and 5 (used only once each) are prime?

2. 12345 can be expressed as the sum of two primes in exactly one way. What is the larger of the two primes whose sum is 12345?

3a. Find all prime numbers p such that 2p+1 is a perfect square.

3b. Find all prime numbers p such that 2p+1 is a perfect cube.

4a. Let n be an integer greater than 6. Prove that if n-1 and n+1 are both prime, then n�(n�+16) is divisible by 720.

4b. Is the converse true?  That is, if n�(n�+16) is divisible by 720, then are n-1 and n+1 both prime?

5. Let a be the integer whose base 10 representation consists of 119 ones. Prove that a is not prime.

6. Prove composite: n⁴+4ⁿ, n>1.

7. Find the set of all positive primes that are a factor of two consecutive terms n²+3

Source: various sources

Solution

1. How many of the three digit numbers that can be made from all of the the digits 1, 3 and 5 (used only once each) are prime?

None of them!  All permutations of 135 are multiples of 3.

2. 12345 can be expressed as the sum of two primes in exactly one way. What is the larger of the two primes whose sum is 12345?

12343.  Two odds add up to an even, so one of the primes must be 2.

3a. Find all prime numbers p such that 2p+1 is a perfect square.

Answer: there are none.  Here's why: Assume 2p+1 is a perfect square.  2p+1 is odd, and all odd perfect squares are equivalent to 1 (mod 4), so 2p is equivalent to 0 (mod 4), in other words it is a multiple of 4.  That means p is even, so it must be 2, the only even prime number.  But 2*2+1=5, which is not a perfect square.

3b. Find all prime numbers p such that 2p+1 is a perfect cube.

Answer: p=13 is the only solution.  Here's why (solution by Chris Braun): Assume 2p+1 is a cube.

2p = q³-1 = (q-1)(q²+q+1)

Both factors of the RHS are at least 2, because q is odd and bigger than 1.  2p is the product of two primes, so if 2p=ab, and both a and b are larger than 1, then a=2 and b=p or vice versa.  q-1 is even, and so it must be 2, so q=3, which makes q²+q+1 equal to 13.

Alternative solution: A quick test reveals p can't be 2, so p is odd.  Let p=2k+1.
2p+1 = 2(2k+1)+1 = 4k+3 = q^3 for some integer, q.
q^3 = 3 (mod 4), so q must also be equivalent to 3 (mod 4).
   (To see this, observe that 0^3, 1^3, and 2^3 have residues (mod 4) of 0, 1, and 0, respectively, not 3 as required.)
let q = 4n+3.  Then,
2p+1 = 4k+3 = q^3 = (4n+3)^3 = 64n^3+144n^2+108n+27.
Subtract 1 from both sides, and divide by 2 to solve for p in terms of n:
p=32n^3+72n^2+54n+13, which factors nicely as
p=(2n+1)(16n^2+28n+13), so if p is prime, n must equal zero (or -1, but a quick test eliminates that), so p=13 is the only prime number that satisfies 2p+1=x^3

4a. Let n be an integer greater than 6. Prove that if n-1 and n+1 are both prime, then n²(n²+16) is divisible by 720.

n is divisible by 6, so n² is divisible by 36 and (n²+16) is divisible by 4, so n²(n²+16) is divisible by 144.  Then 5 is the only additional factor we need to find in order to show the result.

If n=1 (mod 5) then n-1 isn't prime, and if n=-1 (mod 5) then n+1 isn't prime, so n must be 0, 2, or 3 (mod 5), so we'll consider those three cases:

case n=0 (mod 5): n² is divisible by 5, and the result follows. 
case n=2 (mod 5): n²+16 is 2²+1=0 (mod 5), and the result follows. 
case n=3 (mod 5): n²+16 is 3²+1=0 (mod 5), and the result follows. 

4b. Is the converse true?  That is, if n²(n²+16) is divisible by 720, then are n-1 and n+1 both prime?

No, the converse is not true, because n²(n²+16) is divisible by 720 whenever n is a multiple of 6 and n≡0, 2, or 3 (mod 5).
To find a counterexample, n-1 or n+1 must be the product of prime factors larger than 5, so n=48 is the smallest counterexample.
If n=48, then n²(n²+16) is divisible by 720, but n+1=49 is not prime.

5. Let a be the integer whose base 10 representation consists of 119 ones. Prove that a is not prime.

Let's look at some smaller examples of numbers consisting of a composite number of ones.  111111 has 6 1's, so it is the product of 010101 and 11.  111111111111111 has 15 1's, so it is the product of 001001001001001 and 111.

119 = 7 * 17, so it's the product of 00000010000001...0000001 and 1111111.

In general, if k is a factor of n, then (x^k-1+x^k-2+...+1) is a factor of (x^n-1+x^n-2+...+1).  Application of this general principle comes with x=10, k=7, and n=119.

6. Prove composite: n⁴+4ⁿ, n>1.

If n is even, then n⁴+4ⁿ is even, so consider the case in which n is odd.

Let n=2k+1, so now we need to show that n⁴+4^2k+1 is composite for any k > 0.

n⁴+4^2k+1 = (n²+2^2k+1-2^k+1n)(n²+2^2k+1+2^k+1n)

This clever factorization uses the trick that:

a⁴+4b⁴  =  (a²+2b²-2ab)(a²+2b²+2ab)

and since n⁴+4^2k+1 = n⁴+(4)(2^4k), we can let a=n and b=2^k to achieve the desired result.

7. Find the set of all positive primes that are a factor of two consecutive terms of n²+3

The answer is {13}.  Here's a solution: Let r,s be two consecutive values of n, and r²+3, s�+3 are both divisible by p.  So

−3=r² (mod p),
−3=s² (mod p), and
s=r+1 (mod p)

Since r and s are two different square roots of −3 (mod p), we also have

s+r=0 (mod p)

These conditions are sufficient to conclude it must be the case that

r=(p−1)/2 (mod p), and
s=(p+1)/2 (mod p).

So then we have the product of the two square roots of −3 is 3, i.e.,

(p−1)(p+1)/4 = 3 (mod p)
p²−1 = 12 (mod p), which is legal since 4 and p are coprime,
p² = 13 (mod p)
0 = 13 (mod p)

So 13 is the only prime that answers this question, and in fact 6²+3=39 and 7²+3=52 are both divisible by 13.

More about this puzzle

(none)

Internet references

(none)

Related pages in this website

(none)

The webmaster and author of this Math Help site is Graeme McRae.