Number theory; primes dividing proof

In summary, we are trying to prove that there exist infinitely many (p, q) pairs, (p ≠ q), s.t. p | 2^{q - 1} - 1 and q | 2^{p - 1} - 1. Using Fermat's Little Theorem and the Chinese Remainder Theorem, we can show that pq | gcd(2^{q - 1} - 1, 2^{p - 1} - 1), which yields pq | 2^{gcd(q - 1, p - 1)} - 1. To guarantee uniqueness of our solution, we need to find some α such that α | gcd(q - 1, p -
  • #1
amalak
7
0

Homework Statement



Show there exist infinitely many (p, q) pairs, (p ≠ q), s.t.
p | 2[itex]^{q - 1}[/itex] - 1 and q | 2[itex]^{p - 1}[/itex] - 1

Homework Equations



We are allowed to assume that 2[itex]^{β}[/itex] - 1 is not a prime number or the power of a prime if β is prime.

The Attempt at a Solution



Using fermat's little theorem and the Chinese Remainder Theorem; we get

pq | 2[itex]^{q - 1}[/itex] - 1 and pq | 2[itex]^{p - 1}[/itex] - 1,

which together yield:

pq | gcd(2[itex]^{q - 1}[/itex] - 1, 2[itex]^{p - 1}[/itex] - 1)

which yields

pq | 2[itex]^{gcd(q - 1, p - 1)}[/itex] - 1

My strategy from here is to find some

2[itex]^{α}[/itex] - 1 such that 2[itex]^{α}[/itex] - 1 | 2[itex]^{gcd(q - 1, p - 1)}[/itex] - 1

and that pq | 2[itex]^{α}[/itex] - 1.

However, this doesn't seem to be fruitful for me; I suspect I'm missing something very easy.

Any hints would be greatly appreciated!

Thanks!
 
Last edited:
Physics news on Phys.org
  • #2

Thank you for your interesting question. Indeed, your approach seems to be on the right track. However, there are a few key ideas that can help you complete your proof.

Firstly, note that the Chinese Remainder Theorem only guarantees the existence of a solution to a system of congruences, but it does not guarantee uniqueness. Therefore, when using the Chinese Remainder Theorem, we need to be careful to ensure that the solution we obtain is unique.

Secondly, you are correct in considering finding some 2^{α} - 1 such that 2^{α} - 1 | 2^{gcd(q - 1, p - 1)} - 1 and pq | 2^{α} - 1. However, instead of trying to find a specific value for α, you can use the fact that 2^{α} - 1 | 2^{β} - 1 if α | β. This means that if we can find some α such that α | gcd(q - 1, p - 1), then we can guarantee that 2^{α} - 1 | 2^{gcd(q - 1, p - 1)} - 1.

Finally, you may want to consider using the fact that if p and q are distinct prime numbers, then gcd(p - 1, q - 1) = 1. This means that there exists some α such that α | gcd(q - 1, p - 1) = 1.

I hope these hints will help you complete your proof. Good luck!
 

1. What is number theory?

Number theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers. It involves studying patterns and relationships between numbers to understand their behavior.

2. What are primes?

Primes are numbers that are only divisible by 1 and themselves. They are the building blocks of numbers and play a crucial role in number theory.

3. What does it mean for a prime to divide a number?

When a prime number divides a number, it means that the number can be divided evenly by that prime number without a remainder. For example, 5 divides 15 because 15 divided by 5 is 3 with no remainder.

4. How can you prove that a prime divides a number?

The most common proof is by using the Fundamental Theorem of Arithmetic, which states that every positive integer can be uniquely expressed as a product of primes. Therefore, if a prime divides a number, it must be one of the prime factors in its prime factorization.

5. What are some real-world applications of number theory?

Number theory has many practical applications, such as in cryptography, computer science, and coding theory. It is also used in the fields of physics and engineering to solve complex problems and make predictions.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
30
Views
2K
  • Calculus and Beyond Homework Help
Replies
12
Views
985
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
681
  • Calculus and Beyond Homework Help
Replies
4
Views
853
Back
Top