Results 1 to 3 of 3

Thread: 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 $\displaystyle x^2 \equiv 1(modp)$ has exactly two solutions: 1 and p-1

    proof: let $\displaystyle r$ be any solution. SO we have $\displaystyle r^2 - 1 \equiv 0(modp)$ so $\displaystyle p \mid (r+1)(r-1)$ thus $\displaystyle p \mid (r+1) or p \mid (r-1)$ otherwise expressed as $\displaystyle (r+1) \equiv 0(modp) or (r-1) \equiv 0(modp)$. So $\displaystyle 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 $\displaystyle ax \equiv b(modm)$ has no solutions.

    Proof: We can prove this by looking at the contrapositive, which is logically equivalent. So if $\displaystyle (a,m) \mid b$ then $\displaystyle ax \equiv b(modm)$ has a solution. Let r be a solution, so $\displaystyle ar \equiv b(modm)$. Thus, $\displaystyle m \mid (ar-b)$ and there exists an integer k such that $\displaystyle mk \equiv (ar-b)$. Since $\displaystyle (a,m) \mid a$ and $\displaystyle (a,m) \mid (km)$ it follows that $\displaystyle (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
    3
    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 $\displaystyle x^2 \equiv 1(modp)$ has exactly two solutions: 1 and p-1

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


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

    otherwise expressed as $\displaystyle (r+1) \equiv 0(modp) or (r-1) \equiv 0(modp)$. So $\displaystyle 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 $\displaystyle p-1=-1\!\!\pmod p$...


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

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


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

    Fix this.

    Tonio



    Let r be a solution, so $\displaystyle ar \equiv b(modm)$. Thus, $\displaystyle m \mid (ar-b)$ and there exists an integer k such that $\displaystyle mk \equiv (ar-b)$. Since $\displaystyle (a,m) \mid a$ and $\displaystyle (a,m) \mid (km)$ it follows that $\displaystyle (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: Dec 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: Oct 19th 2009, 08:44 PM
  3. Replies: 5
    Last Post: Aug 11th 2009, 06:37 AM
  4. Confirmation needed .
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Feb 23rd 2009, 07:02 AM
  5. locus, need confirmation
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Feb 2nd 2009, 10:34 AM

Search Tags


/mathhelpforum @mathhelpforum