Results 1 to 5 of 5

Thread: congruence existence problem

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    11

    congruence existence problem

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

    prove that if $\displaystyle y^a\equiv1\pmod p$ there exists x such that $\displaystyle 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
    10
    Quote Originally Posted by siegfried View Post
    let p be a prime and suppose $\displaystyle p-1=ab$ for some integers a and b

    prove that if $\displaystyle y^a\equiv1\pmod p$ there exists x such that $\displaystyle y\equiv x^b\pmod p$
    Let $\displaystyle z$ be a primitive root modulo $\displaystyle p$ (we know it exists).
    This means $\displaystyle y\equiv z^c(\bmod p)$ for some $\displaystyle 1\leq c \leq p-1$.
    Since $\displaystyle y^a\equiv 1(\bmod p) \implies (z^c)^a\equiv 1(\bmod p) \implies z^{ac} \equiv 1(\bmod p)$.
    Therefore, $\displaystyle p-1$ divides $\displaystyle ac$, thus $\displaystyle ab|ac \implies b|c$.
    Therefore, $\displaystyle y\equiv z^c = \left( z^{c/b} \right)^b = x^b(\bmod p)$ where $\displaystyle 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 $\displaystyle A=\{y\in\mathbb Z_P^\times:y^a=1\}$ is a subgroup of $\displaystyle \mathbb Z_p^\times=\{1,2,\ldots,p-1\}$ under multiplication modulo $\displaystyle p.$

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

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

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

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

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

    $\displaystyle 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 $\displaystyle \left|f\left(\mathbb Z_p^\times\right)\right|=|A|,$ i.e. $\displaystyle 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 $\displaystyle A=\{y\in\mathbb Z_P^\times:y^a=1\}$ is a subgroup of $\displaystyle \mathbb Z_p^\times=\{1,2,\ldots,p-1\}$ under multiplication modulo $\displaystyle p.$

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

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

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

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

    Now, by the homomorphism theorem, we have $\displaystyle \mathbb Z_p^\times/K\cong f\left(\mathbb Z_p^\times\right)$. And so we have
    $\displaystyle 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 $\displaystyle \left|f\left(\mathbb Z_p^\times\right)\right|=|A|,$ i.e. $\displaystyle 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. $\displaystyle \mathbb{Z}_p^{\times}$ is a cyclic group).
    Last edited by NonCommAlg; Apr 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: Apr 21st 2011, 10:14 AM
  2. Existence of a solution; Initial value problem
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: Dec 3rd 2010, 11:35 PM
  3. Problem regarding appliation of Existence & Uniqueness theorem
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: Mar 18th 2010, 07:17 AM
  4. Problem with a limit's existence...
    Posted in the Calculus Forum
    Replies: 5
    Last Post: Sep 25th 2009, 11:13 AM
  5. Another congruence problem
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: Apr 3rd 2009, 05:14 PM

Search Tags


/mathhelpforum @mathhelpforum