Maths Olympiad Prep

Library / /1 of 13

Number theory Difficulty 5.7 AIME, harder Find the answer

Find all prime numbers p,q,r,kp,q,r,k such that pq+qr+rp=12k+1pq+qr+rp = 12k+1

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To solve the given problem, we need to find all prime numbers p,q,r,k p, q, r, k such that the equation

pq+qr+rp=12k+1 pq + qr + rp = 12k + 1

is satisfied.

### Step-by-Step Solution

1. Analyzing the Equation:

The equation can be written as:

pq+qr+rp=12k+1 pq + qr + rp = 12k + 1

Our goal is to find integer values (specifically prime numbers) for p,q,r, p, q, r, and k k that satisfy the equation.

2. Evaluating Possibilities:

Since p,q,r p, q, r are prime numbers, let's start with small prime numbers and test them.

3. **Setting p=2 p = 2 **:

- Substituting p=2 p = 2 , we get:

2q+qr+2r=12k+1 2q + qr + 2r = 12k + 1

- Rearranging, it becomes:

qr+2(q+r)=12k+1 qr + 2(q + r) = 12k + 1

Let's test with q=3 q = 3 (the next smallest prime number):

4. **Setting q=3 q = 3 **:

- Substituting q=3 q = 3 into the equation, we have:

3r+2(3+r)=12k+1 3r + 2(3 + r) = 12k + 1

- Simplifying, we find:

3r+6+2r=12k+1    5r+6=12k+1    5r=12k5 3r + 6 + 2r = 12k + 1 \implies 5r + 6 = 12k + 1 \implies 5r = 12k - 5

- Therefore, 5r7(mod12) 5r \equiv 7 \pmod{12} . Possible values of r7(mod12) r \equiv 7 \pmod{12} need to be prime.

5. **Trying Possible Values for r r **:

- Let’s check while satisfying 5r7(mod12) 5r \equiv 7 \pmod{12} :

- r=11 r = 11 : when r=11 r = 11 , check:

5(11)+6=55+6=61 5(11) + 6 = 55 + 6 = 61

Check if 61=12k+1 61 = 12k + 1 :

611=60,then k=6012=5 61 - 1 = 60, \, \text{then } k = \frac{60}{12} = 5

- Therefore, (p,q,r,k)=(2,3,11,5)(p, q, r, k) = (2, 3, 11, 5).

6. Considering Permutations:

Due to symmetry in the equation pq+qr+rp pq + qr + rp , permuting (p,q,r)(p, q, r) gives valid solutions without changing the form of the equation:

- Therefore, the valid solutions are:

(p,q,r,k)=(2,3,11,5);(2,11,3,5);(3,11,2,5);(3,2,11,5);(11,2,3,5);(11,3,2,5) (p, q, r, k) = (2, 3, 11, 5); (2, 11, 3, 5); (3, 11, 2, 5); (3, 2, 11, 5); (11, 2, 3, 5); (11, 3, 2, 5)

7. Conclusion:

Thus, all prime number solutions (p,q,r,k)(p, q, r, k) such that the given equation holds are:

(2,3,11,5);(2,11,3,5);(3,11,2,5);(3,2,11,5);(11,2,3,5);(11,3,2,5) \boxed{(2, 3, 11, 5); (2, 11, 3, 5); (3, 11, 2, 5); (3, 2, 11, 5); (11, 2, 3, 5); (11, 3, 2, 5)}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.