Question

Let p, q be prime numbers such that n3pq n is a multiple of 3pq for all positive integers n. Find the least possible value of p + q.

Answer 1

Answer:

28

Step-by-step explanation:

Given  

Let p, q be prime numbers such that n3pq n is a multiple of 3pq for all positive integers n. Find the least possible value of p + q.

n^3pq – n = 0 (mod 3)

n^3pq – n = 0 (mod p)

n^3pq – n = 0 (mod q)

We need to satisfy the terms

1. (3 – 1) l (pq – 1) so pq is odd

2. (p – 1) l (3q – 1)  

3 does not divide 3q – 1 and 3 must not divide p – 1  

Therefore p – 1 = 3k + 1 or 3k + 2 for some integer k.

Implies p = 3k + 2 or 3k + 3

Since it is prime p =/ 3k + 3

Therefore p = 3k + 2 k is odd and p > 3  

So 2 y + 1  

So p = 6y + 5

Now for the second part we get

(q – 1)(3p – 1) so q will also be 5 (mod 6)

Now by trial and error we get least values for p and q as 17 and 11

So p + q = 17 + 11 = 28