Can this number theory problem be solved purely algebraically?

  • Context: Graduate 
  • Thread starter Thread starter Wiz14
  • Start date Start date
  • Tags Tags
    Number theory Theory
Click For Summary

Discussion Overview

The discussion revolves around a number theory problem involving a prime number \( p \) and an integer \( a \) to prove a divisibility condition. Participants explore whether the problem can be solved purely algebraically and examine the implications of the proof structure, particularly the necessity of demonstrating both directions of an "if and only if" statement.

Discussion Character

  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant proposes that \( a \) divides \( p + 1 \) implies the existence of integers \( m \) and \( n \) such that \( \frac{a}{p} = \frac{1}{m} + \frac{1}{n} \).
  • Another participant questions whether the proof adequately uses the fact that \( p \) is prime and whether \( m \) and \( n \) are indeed integers.
  • A different participant confirms that the proof is valid in one direction but emphasizes that the reverse direction has not yet been established.
  • Further clarification is sought on how to structure the proof to demonstrate the "if and only if" nature of the statement.
  • Concerns are raised about the clarity and completeness of the initial proof, particularly regarding the necessity of proving both directions of the statement.

Areas of Agreement / Disagreement

Participants generally agree that the problem can be approached algebraically, but there is disagreement on whether the proof provided is complete and whether it sufficiently addresses the conditions required for both directions of the statement.

Contextual Notes

Participants note the importance of using the primality of \( p \) in the proof, which remains unaddressed in the initial arguments. There is also a focus on ensuring that all integers involved are clearly defined and that the proof structure adheres to the requirements of an "if and only if" statement.

Wiz14
Messages
20
Reaction score
0
Let p be a prime number and 1 <= a < p be an integer.

Prove that a divides p + 1 if and only if there exist integers m and n such that
a/p = 1/m + 1/n

My solution: a|p+1 then there exists an integer m such that am = p+1
Dividing by mp
a/p = 1/m + 1/mp
So if I choose n = mp(which is always an integer) am I done?
 
Physics news on Phys.org
The answer to your title question is, yes. These things are usually solved algebraically. Just requires a bit of reasoning as you can see.

It looks like a good start but it's not that clear to me. It doesn't mean your proof is wrong, it just means it doesn't convince me yet. My questions are:

Have we even used the fact that p is prime?

Have we really shown that m and n are integers?

Have we shown what the proof is asking in the sense that this is true both ways? (iff and only if?). Typically this requires you to structure your proof as a string of "iff" or "if and only if" statements, or to prove it both ways (if P then Q, then if Q then P).

-Dave K
 
Your proof is fine one way. That is, you have proved "if a divides p+1, then there exist integers, m and n, such that a/p= 1/m+ 1/n".

But this is an "if and only if" statement. You have NOT YET proved the other way "if there exist integers, m and n, such that a/p= 1/m+ 1/n, then a divides p+1". That might be where you need to use "p is prime".
 
dkotschessaa said:
The answer to your title question is, yes. These things are usually solved algebraically. Just requires a bit of reasoning as you can see.

It looks like a good start but it's not that clear to me. It doesn't mean your proof is wrong, it just means it doesn't convince me yet. My questions are:

Have we even used the fact that p is prime?

Have we really shown that m and n are integers?

Have we shown what the proof is asking in the sense that this is true both ways? (iff and only if?). Typically this requires you to structure your proof as a string of "iff" or "if and only if" statements, or to prove it both ways (if P then Q, then if Q then P).

-Dave K

Thank you for your response.
The main reason I posted this question, and the reason I doubt my solution is correct, is because as you said we haven't used the fact that p is prime. But I cannot find any mistakes. I will try to better explain my answer.

By definition, a divides p+1 means that there exists an integer m such that am=p+1.
Now dividing both sides of the equation by mp, the equation becomes a/p=1/m +1/mp. Since p and m are integers, m*p=n is an integer. So we have proven the forward direction. To go backwards we can do the reverse operations on a/p=1/m + 1/mp to get am = p+1 which means that a divides p+1.
 

Similar threads

  • · Replies 12 ·
Replies
12
Views
1K
Replies
48
Views
6K
  • · Replies 21 ·
Replies
21
Views
2K
  • · Replies 31 ·
2
Replies
31
Views
3K
  • · Replies 17 ·
Replies
17
Views
2K
  • · Replies 17 ·
Replies
17
Views
3K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 5 ·
Replies
5
Views
3K