Results 1 to 3 of 3

Math Help - Just need confirmation

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    2

    Just need confirmation

    Hi, I just registered for this site, and it looks like a pretty neat place.
    I just needed a confirmation that I did a couple proofs right. I'm taking Number Theory at my university, and on Tuesday I have to teach the class two proofs.

    My first one is to prove that x^2 \equiv 1(modp) has exactly two solutions: 1 and p-1

    proof: let r be any solution. SO we have r^2 - 1 \equiv 0(modp) so p \mid (r+1)(r-1) thus p \mid (r+1) or  p \mid (r-1) otherwise expressed as (r+1) \equiv 0(modp) or (r-1) \equiv 0(modp). So r \equiv p-1(modp) or r \equiv 1(modp). Since r is a least residue (modp) we have r = p -1 or 1

    The other one I have to do is prove that if (a,m) doesnt divide b, then ax \equiv b(modm) has no solutions.

    Proof: We can prove this by looking at the contrapositive, which is logically equivalent. So if (a,m) \mid b then ax \equiv b(modm) has a solution. Let r be a solution, so ar \equiv b(modm). Thus, m \mid (ar-b) and there exists an integer k such that mk \equiv (ar-b). Since (a,m) \mid a and (a,m) \mid (km) it follows that (a,m) \mid b

    Thanks guys I appreciate it
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by skyzo View Post
    Hi, I just registered for this site, and it looks like a pretty neat place.
    I just needed a confirmation that I did a couple proofs right. I'm taking Number Theory at my university, and on Tuesday I have to teach the class two proofs.

    My first one is to prove that x^2 \equiv 1(modp) has exactly two solutions: 1 and p-1

    proof: let r be any solution. SO we have r^2 - 1 \equiv 0(modp) so p \mid (r+1)(r-1) thus p \mid (r+1) or  p \mid (r-1)


    Because p is a prime (this is important) . Correct.

    otherwise expressed as (r+1) \equiv 0(modp) or (r-1) \equiv 0(modp). So r \equiv p-1(modp) or r \equiv 1(modp). Since r is a least residue (modp) we have r = p -1 or 1


    Correct. Note that p-1=-1\!\!\pmod p...


    The other one I have to do is prove that if (a,m) doesnt divide b, then ax \equiv b(modm) has no solutions.

    Proof: We can prove this by looking at the contrapositive, which is logically equivalent. So if (a,m) \mid b then ax \equiv b(modm) has a solution.


    This is not the contrapositive! It is "if ax=b\!\!\pmod m has a solution then (a,m)\mid b .

    Fix this.

    Tonio



    Let r be a solution, so ar \equiv b(modm). Thus, m \mid (ar-b) and there exists an integer k such that mk \equiv (ar-b). Since (a,m) \mid a and (a,m) \mid (km) it follows that (a,m) \mid b

    Thanks guys I appreciate it
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2011
    Posts
    2
    Thanks tonio, I will fix those things before tuesday.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. confirmation?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 28th 2009, 05:40 PM
  2. Need a little confirmation on limit of tan(x)/x
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 19th 2009, 08:44 PM
  3. Replies: 5
    Last Post: August 11th 2009, 06:37 AM
  4. Confirmation needed .
    Posted in the Algebra Forum
    Replies: 4
    Last Post: February 23rd 2009, 07:02 AM
  5. locus, need confirmation
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: February 2nd 2009, 10:34 AM

Search Tags


/mathhelpforum @mathhelpforum