Can this number theory problem be solved purely algebraically?


by Wiz14
Tags: algebraically, number, purely, solved, theory
Wiz14
Wiz14 is offline
#1
Feb11-13, 10:01 PM
P: 20
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?
Phys.Org News Partner Science news on Phys.org
Lemurs match scent of a friend to sound of her voice
Repeated self-healing now possible in composite materials
'Heartbleed' fix may slow Web performance
dkotschessaa
dkotschessaa is online now
#2
Feb12-13, 08:36 AM
dkotschessaa's Avatar
P: 519
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
HallsofIvy
HallsofIvy is offline
#3
Feb12-13, 09:20 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,879
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".

Wiz14
Wiz14 is offline
#4
Feb12-13, 09:29 AM
P: 20

Can this number theory problem be solved purely algebraically?


Quote Quote by dkotschessaa View Post
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.


Register to reply

Related Discussions
Can all limits questions be solved algebraically? Calculus & Beyond Homework 2
Can someone show me how this is solved algebraically Calculus & Beyond Homework 6
Maximum - Can this be solved algebraically? Calculus & Beyond Homework 2
Pi(x) function in number theory solved... Linear & Abstract Algebra 39
Pi(x) function in number theory solvedĦĦĦ General Math 7