Can this number theory problem be solved purely algebraically?

In summary: Therefore, we have proven the statement in both directions, proving it is an if and only if statement.In summary, we have shown that a divides p+1 if and only if there exist integers m and n such that a/p=1/m + 1/n, using algebraic reasoning and the fact that p is prime.
  • #1
Wiz14
20
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
  • #2
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
 
  • #3
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".
 
  • #4
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.
 
  • #5


Yes, your solution is correct. By choosing n=mp, we can rewrite the equation as a/p = 1/m + 1/n, where both m and n are integers. This shows that the statement "a divides p+1" implies the existence of integers m and n satisfying the equation. Conversely, if we assume the existence of integers m and n such that a/p = 1/m + 1/n, we can multiply both sides by p and get ap = m+n, which implies that a divides m+n. Since a also divides m and n (since they are integers), it must also divide their sum, which is p+1. Therefore, we have shown that the statement "there exist integers m and n such that a/p = 1/m + 1/n" implies that "a divides p+1". Hence, the statement "a divides p+1 if and only if there exist integers m and n such that a/p = 1/m + 1/n" is true.
 

1. Can all number theory problems be solved purely algebraically?

No, not all number theory problems can be solved purely algebraically. Some problems require techniques from other branches of mathematics, such as geometry or calculus, to be solved.

2. What is the advantage of solving a number theory problem algebraically?

The advantage of solving a number theory problem algebraically is that it provides a more rigorous and systematic approach to finding a solution. It also allows for generalizations and can lead to new insights and discoveries.

3. Are there any specific strategies or techniques for solving number theory problems algebraically?

Yes, there are specific strategies and techniques for solving number theory problems algebraically, such as using properties of prime numbers, modular arithmetic, and number patterns. These strategies can be learned and applied to various problems.

4. Can a number theory problem be solved algebraically if it involves complex numbers?

Yes, a number theory problem can be solved algebraically even if it involves complex numbers. Complex numbers can be represented and manipulated algebraically using their real and imaginary parts.

5. Are there any limitations to solving a number theory problem algebraically?

Yes, there can be limitations to solving a number theory problem algebraically. Some problems may require advanced techniques or may be so complex that they cannot be solved purely algebraically. In these cases, a combination of algebra and other mathematical methods may be needed.

Similar threads

  • Linear and Abstract Algebra
Replies
8
Views
855
  • Linear and Abstract Algebra
Replies
1
Views
888
  • Linear and Abstract Algebra
Replies
4
Views
725
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
705
  • Linear and Abstract Algebra
Replies
1
Views
730
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
899
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
Back
Top