Maths Olympiad Prep

Library / /5 of 520

Number theory Difficulty 6.1 National olympiad Find the answer

Find all primes p,qp,q such that pp divides 30q130q-1 and qq divides 30p130p-1.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve the problem, we need to find all prime numbers p p and q q such that p p divides 30q1 30q - 1 and q q divides 30p1 30p - 1 .

1. Initial Setup:
Given the conditions:
p(30q1)andq(30p1) p \mid (30q - 1) \quad \text{and} \quad q \mid (30p - 1)
This implies there exist integers a a and b b such that:
30q1=apand30p1=bq 30q - 1 = ap \quad \text{and} \quad 30p - 1 = bq

2. Combining the Equations:
We can rewrite the equations as:
30q=ap+1and30p=bq+1 30q = ap + 1 \quad \text{and} \quad 30p = bq + 1
Adding these two equations, we get:
30q+30p=ap+bq+2 30q + 30p = ap + bq + 2
Rearranging, we have:
30(p+q)=ap+bq+2 30(p + q) = ap + bq + 2

3. **Exploring Possible Values of k k :**
Let k=30(p+q)2pq k = \frac{30(p + q) - 2}{pq} . Since k k must be an integer, we need to find values of k k such that:
k(pq)=30(p+q)2 k(pq) = 30(p + q) - 2
Given that k k must be a divisor of 30 30 and gcd(30,k)=1 \gcd(30, k) = 1 , the possible values of k k are 1,7,11,13,17,19,23,29 1, 7, 11, 13, 17, 19, 23, 29 .

4. **Analyzing Each k k :**
- For k=1 k = 1 :
pq=30(p+q)2 pq = 30(p + q) - 2
Rearranging, we get:
pq30p30q+2=0 pq - 30p - 30q + 2 = 0
Solving this quadratic equation in terms of p p and q q , we find:
(p30)(q30)=899 (p - 30)(q - 30) = 899
The factor pairs of 899 are (1,899) (1, 899) and (29,31) (29, 31) . Since p p and q q are primes, the valid pairs are:
(p,q)=(59,61)and(61,59) (p, q) = (59, 61) \quad \text{and} \quad (61, 59)

- For k=7 k = 7 :
7pq=30(p+q)2 7pq = 30(p + q) - 2
Rearranging, we get:
(7p30)(7q30)=893 (7p - 30)(7q - 30) = 893
The factor pairs of 893 are (1,893) (1, 893) and (19,47) (19, 47) . Since p p and q q are primes, the valid pairs are:
(p,q)=(7,11)and(11,7) (p, q) = (7, 11) \quad \text{and} \quad (11, 7)

- For k=11 k = 11 :
11pq=30(p+q)2 11pq = 30(p + q) - 2
Rearranging, we get:
(11p30)(11q30)=889 (11p - 30)(11q - 30) = 889
The factor pairs of 889 are (1,889) (1, 889) and (23,37) (23, 37) . Since p p and q q are primes, there are no valid pairs.

5. Conclusion:
The valid pairs of primes (p,q) (p, q) that satisfy the given conditions are:
(p,q)=(7,11),(11,7),(59,61),(61,59) (p, q) = (7, 11), (11, 7), (59, 61), (61, 59)

The final answer is (7,11),(11,7),(59,61),(61,59)\boxed{(7, 11), (11, 7), (59, 61), (61, 59)}.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.