Results 1 to 5 of 5

Math Help - congruence existence problem

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    11

    congruence existence problem

    let p be a prime and suppose p-1=ab for some integers a and b

    prove that if y^a\equiv1\pmod p there exists x such that y\equiv x^b\pmod p
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by siegfried View Post
    let p be a prime and suppose p-1=ab for some integers a and b

    prove that if y^a\equiv1\pmod p there exists x such that y\equiv x^b\pmod p
    Let z be a primitive root modulo p (we know it exists).
    This means y\equiv z^c(\bmod p) for some 1\leq c \leq p-1.
    Since y^a\equiv 1(\bmod p) \implies (z^c)^a\equiv 1(\bmod p) \implies z^{ac} \equiv 1(\bmod p).
    Therefore, p-1 divides ac, thus ab|ac \implies b|c.
    Therefore, y\equiv z^c = \left( z^{c/b} \right)^b = x^b(\bmod p) where x=z^{c/b}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    11
    what is a primitive root modulo p?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Hereís another proof.

    Notice that A=\{y\in\mathbb Z_P^\times:y^a=1\} is a subgroup of \mathbb Z_p^\times=\{1,2,\ldots,p-1\} under multiplication modulo p.

    Define a mapping f:\mathbb Z_p^\times\to A by f(x)=x^b. This makes sense because \forall x\in\mathbb Z_p^\times, (x^b)^a=x^{p-1}=1 by Fermatís little theorem, so that x^b\in A.

    f is clearly a homomorphism and so its image is a subgroup of A. \therefore\ \left|f\left(\mathbb Z_p^\times\right)\right|\leqslant|A|.

    Now A consists of roots of the polynomial x^a-1 of degree a in \mathbb Z_p^\times[x], and there cannot be more than a such roots. \therefore\ |A|\leqslant a.

    Similarly, the kernel of f, K=\{x\in\mathbb Z_p^\times:x^b=1\} consists of roots of the polynomial x^b-1 of degree b in \mathbb Z_p^\times[x], and so |K|\leqslant b.

    Now, by the homomorphism theorem, we have \mathbb Z_p^\times/K\cong f\left(\mathbb Z_p^\times\right). And so we have

    ab=p-1=\left|\mathbb Z_p^\times\right|=\left|f\left(\mathbb Z_p^\times\right)\right|\cdot|K|\leqslant|A|\cdot|  K|\leqslant ab

    Therefore we actually have \left|f\left(\mathbb Z_p^\times\right)\right|=|A|, i.e. f is surjective. This proves the theorem.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by JaneBennet View Post
    Here’s another proof.

    Notice that A=\{y\in\mathbb Z_P^\times:y^a=1\} is a subgroup of \mathbb Z_p^\times=\{1,2,\ldots,p-1\} under multiplication modulo p.

    Define a mapping f:\mathbb Z_p^\times\to A by f(x)=x^b. This makes sense because \forall x\in\mathbb Z_p^\times, (x^b)^a=x^{p-1}=1 by Fermat’s little theorem, so that x^b\in A.

    f is clearly a homomorphism and so its image is a subgroup of A. \therefore\ \left|f\left(\mathbb Z_p^\times\right)\right|\leqslant|A|.

    Now A consists of roots of the polynomial x^a-1 of degree a in \mathbb Z_p^\times[x], and there cannot be more than a such roots. \therefore\ |A|\leqslant a.

    Similarly, the kernel of f, K=\{x\in\mathbb Z_p^\times:x^b=1\} consists of roots of the polynomial x^b-1 of degree b in \mathbb Z_p^\times[x], and so |K|\leqslant b.

    Now, by the homomorphism theorem, we have \mathbb Z_p^\times/K\cong f\left(\mathbb Z_p^\times\right). And so we have
    ab=p-1=\left|\mathbb Z_p^\times\right|=\left|f\left(\mathbb Z_p^\times\right)\right|\cdot|K|\leqslant|A|\cdot|  K|\leqslant ab
    Therefore we actually have \left|f\left(\mathbb Z_p^\times\right)\right|=|A|, i.e. f is surjective. This proves the theorem.
    this is a pretty solution! it shows you've got to be creative if you insist on not using standard facts (here the one that ThePerfectHacker used, i.e. \mathbb{Z}_p^{\times} is a cyclic group).
    Last edited by NonCommAlg; April 10th 2009 at 01:59 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Perfect Cuboid Problem: Existence Proof
    Posted in the Peer Math Review Forum
    Replies: 0
    Last Post: April 21st 2011, 10:14 AM
  2. Existence of a solution; Initial value problem
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: December 3rd 2010, 11:35 PM
  3. Problem regarding appliation of Existence & Uniqueness theorem
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: March 18th 2010, 07:17 AM
  4. Problem with a limit's existence...
    Posted in the Calculus Forum
    Replies: 5
    Last Post: September 25th 2009, 11:13 AM
  5. Another congruence problem
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 3rd 2009, 05:14 PM

Search Tags


/mathhelpforum @mathhelpforum