Results 1 to 2 of 2

Math Help - Roots over Z/pZ

  1. #1
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Roots over Z/pZ

    Hello there,
    my book is asking to do the following problem :

    Given x^a \equiv x \pmod{n}, design an algorithm to find x in polynomial time know a and n, and given that the modulus n is composite.
    Isn't there a typo in the last word, because I know about ways to take roots over \mathbb{Z}/p\mathbb{Z} when p is a prime, which is not the case here, and as I looked over the internet, it seems a "hard" problem to take roots if p is a composite ?

    And also, if I know that x^a \equiv x \pmod{n}, then the following must be true : x^{a - 1} \equiv 1 \pmod{n}, by dividing both sides by x. However, if I take an example, say n = 21, x = 7 and a = 3, we have 7^3 \equiv 7 \pmod{21} alright, but 7^2 \equiv 7 \pmod{21} and is not equal to one, however 2 = 3 - 1. Anyone know what I messed up here ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    We can multiply residu-classes, not "allways" divide them:
    We can only divide classes when we're working in the group (\mathbb{Z}/n\mathbb{Z})^*.

    In your example you used n = 21, and 7|21. Observe that 3\cdot 7 \equiv 9\cdot 7 \equiv 0 mod 21. But it's not true that 7\equiv 0 mod 21.

    You're getting into trouble when you're using elements that divide n.
    The conclusion is: x^a \equiv x mod n \Leftrightarrow x^{a-1}\equiv 1 mod n iff gcd(x,n) = 1.

    We can draw the following conclusion:

    x^a\equiv x mod n  \Leftrightarrow x(x^{a-1}-1)\equiv 0 mod n.

    Hence we have the following cases:

    Let x\in \mathbb{Z}/n\mathbb{Z}
    1. x is a root if: x\equiv 0 mod n.
    2. if \phi(n)|a-1 then all x\in (\mathbb{Z}/n\mathbb{Z})^* are roots, ie. all x\in \mathbb{Z}/n\mathbb{Z} with gcd(x,n) = 1. And x with gcd(x,n) \neq 1 can be roots.
    3. a-1|\phi(n). Then only elements from the group (\mathbb{Z}/n\mathbb{Z})^* that have order a-1 are roots. And x with gcd(x,n) \neq 1 can be roots.
    4. If neither a-1|\phi(n) or \phi(n)|a-1 then only x, with gcd(x,n) \neq 1 can be roots.

    I hope you know the Euler totient function a little. For more about the euler totient function: Euler's totient function - Wikipedia, the free encyclopedia

    Finding roots for all x\in \mathbb{Z}/n\mathbb{Z} with gcd(x,n) \neq 1 is indeed a hard problem.
    Last edited by Dinkydoe; January 20th 2010 at 09:42 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. roots
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 24th 2010, 03:50 AM
  2. Roots & Imaginary Roots
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: October 4th 2009, 10:24 AM
  3. roots
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 29th 2009, 06:27 AM
  4. Roots ><
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 7th 2008, 09:49 AM
  5. Given 2 imaginary roots find other 2 roots
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: January 26th 2008, 10:24 PM

Search Tags


/mathhelpforum @mathhelpforum