To solve the problem, we need to find all prime numbers p and q such that p divides 30q−1 and q divides 30p−1.
1. Initial Setup:
Given the conditions:
p∣(30q−1)andq∣(30p−1)
This implies there exist integers a and b such that:
30q−1=apand30p−1=bq
2. Combining the Equations:
We can rewrite the equations as:
30q=ap+1and30p=bq+1
Adding these two equations, we get:
30q+30p=ap+bq+2
Rearranging, we have:
30(p+q)=ap+bq+2
3. **Exploring Possible Values of k:**
Let k=pq30(p+q)−2. Since k must be an integer, we need to find values of k such that:
k(pq)=30(p+q)−2
Given that k must be a divisor of 30 and gcd(30,k)=1, the possible values of k are 1,7,11,13,17,19,23,29.
4. **Analyzing Each k:**
- For k=1:
pq=30(p+q)−2
Rearranging, we get:
pq−30p−30q+2=0
Solving this quadratic equation in terms of p and q, we find:
(p−30)(q−30)=899
The factor pairs of 899 are (1,899) and (29,31). Since p and q are primes, the valid pairs are:
(p,q)=(59,61)and(61,59)
- For k=7:
7pq=30(p+q)−2
Rearranging, we get:
(7p−30)(7q−30)=893
The factor pairs of 893 are (1,893) and (19,47). Since p and q are primes, the valid pairs are:
(p,q)=(7,11)and(11,7)
- For k=11:
11pq=30(p+q)−2
Rearranging, we get:
(11p−30)(11q−30)=889
The factor pairs of 889 are (1,889) and (23,37). Since p and q are primes, there are no valid pairs.
5. Conclusion:
The valid pairs of primes (p,q) that satisfy the given conditions are:
(p,q)=(7,11),(11,7),(59,61),(61,59)
The final answer is (7,11),(11,7),(59,61),(61,59).