Results 1 to 4 of 4

Math Help - Congruence problems

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    9

    Congruence problems

    hi everyone

    anyone up for taking a look at these congruence proofs? ;3


    5. (a) Prove that if p is a prime, then the only solutions of x^2 congruent to 1 (mod p) are integers x such that x congruent to 1 (mod p) or x congruent to −1 (mod p).

    (b) Suppose that p is not a prime. Then does the statement stay valid, i.e., the only solutions of x^2 congruent to 1 (mod p) are integers x such that x congruent to 1 (mod p) or x congruent to −1 (mod p). Give a
    proof or a counterexample.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by jessicafreeman View Post
    hi everyone

    anyone up for taking a look at these congruence proofs? ;3


    5. (a) Prove that if p is a prime, then the only solutions of x^2 congruent to 1 (mod p) are integers x such that x congruent to 1 (mod p) or x congruent to −1 (mod p).


    The quotient ring \mathbb{F}_p:=\mathbb{Z}\slash p\mathbb{Z}\,,\,\,p a prime, is in fact a field, and thus any polynomial with coefficients in it has at most n= of the polynomial different roots, so x^2=1\!\!\!\pmod p\Longleftrightarrow (x-1)(x+1)=0\!\!\!\pmod p \Longleftrightarrow x=\pm 1 \!\!\!\pmod p


    (b) Suppose that p is not a prime. Then does the statement stay valid, i.e., the only solutions of x^2 congruent to 1 (mod p) are integers x such that x congruent to 1 (mod p) or x congruent to −1 (mod p). Give a
    proof or a counterexample.


    Count how many elements are there in \mathbb{Z}\slash 8\mathbb{Z} which fulfill x^2=1\!\!\!\pmod 8

    Tonio

    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    2
    Quote Originally Posted by tonio View Post
    .
    I am having trouble understanding your solution to (a), possibly because i am dumb. Can you please explain it in a different fashion.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by DKman View Post
    I am having trouble understanding your solution to (a), possibly because i am dumb. Can you please explain it in a different fashion.

    Let's try this as follows, which is basically the same way but with more detail, doing operations modulo p all the way long:

    x^2=1\Longleftrightarrow x^2-1=0\Longleftrightarrow (x-1)(x+1)=0 .

    Since \mathbb{F}_p:=\mathbb{Z}\slash p\mathbb{Z} is a field (in fact it is enough that it is an integral domain), the last equality above is possible iff  x=1\,\,\,or\,\,\,x=-1 , otherwise we'd have non-trivial divisors of zero.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. some of congruence problems
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 16th 2011, 04:28 AM
  2. Congruence Problems
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 18th 2010, 10:30 PM
  3. Help With Congruence Problems
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 23rd 2009, 10:05 AM
  4. Help with understanding congruence problems
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 26th 2009, 02:56 AM
  5. Congruence problems
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 11th 2009, 11:15 AM

Search Tags


/mathhelpforum @mathhelpforum