Results 1 to 11 of 11

Math Help - Proof with reduced residue systems

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    14

    Proof with reduced residue systems

    Let r_{1}, r_{2},...,r_{n} be a reduced residue system modulo m (n = ф(m)).
    Show that the numbers r_{1}^k, r_{2}^k,..., r_{n}^k form a reduced residue system
    (mod m) if and only if (k, ф(m)) = 1.

    I am thinking of letting g be a primitive root modulo m, so that g, g^2,... g^{\phi(m)} will be a reduced residue system. Then, somehow, g^k, g^{2k},... g^{\phi(m)k} will be a reduced residue system if (k, ф(m)) = 1.

    Could anyone help me prove this? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by ilikecandy View Post
    Let r_{1}, r_{2},...,r_{n} be a reduced residue system modulo m (n = ф(m)).
    Show that the numbers r_{1}^k, r_{2}^k,..., r_{n}^k form a reduced residue system
    (mod m) if and only if (k, ф(m)) = 1.

    I am thinking of letting g be a primitive root modulo m, so that g, g^2,... g^{\phi(m)} will be a reduced residue system. Then, somehow, g^k, g^{2k},... g^{\phi(m)k} will be a reduced residue system if (k, ф(m)) = 1.

    Could anyone help me prove this? Thanks.
    Hint: if G=<g> is a cyclic group of order m, then G=<g^k>\Longleftrightarrow (k,m)=1

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    14
    Thanks for the response, but I haven't learned what cyclic groups are in my class.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Your idea to use primitive root is not bad, but you have to be careful because primitive roots do not always exist. For instance if you look at a reduced system modulo 8, you will find that the square of every element is the identity! (Tonio, you should also take note of this. Your hint is misleading!)

    So we need a different approach here.

    Suppose (k,\phi(m))=1. It should be clear that the numbers \{r_1^k,\hdots,r_n^k\} form a reduced system if and only if no two of them are congruent \mod m - i.e. if and only if the map f: r \mapsto r^k is a bijection. So it suffices to show that this map is invertible. Since (k,n)=1, we can find integers x,y such that xk+yn=1. Now let g:r\mapsto r^x. Then gf(r)=g(r^k)=r^{kx}=r^{1-yn}=r. So the map is invertible, and we are done.

    Can you do the other direction now?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    14
    Thank you very much! I am not that great with sets, so I have a question. Does f: r \mapsto r^k mean that f(r)=r^k?
    Also, how do you know that 1-yn=1, or that yn=0?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    You are very welcome.

    Yes, that is what r \mapsto r^k means.

    It's not quite that yn=0. It's because you have r^n \equiv 1 \mod m (and hence that r^{tn} \equiv 1 also for all integers t). You probably know this statement in the form of Euler's theorem.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2009
    Posts
    14
    I meant how did you get gf(r)=g(r^k)=r^{kx}=r^{1-yn}=r
    From r^{1-yn}=r?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Euler's theorem states that r^{\phi(m)} \equiv 1 \mod m. So r^{1-yn} \equiv r\times (r^{-1})^{yn} \equiv r \times 1^y \equiv r.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2009
    Posts
    14
    Thanks, I didn't see that.

    So the other direction would go as follows:

    Let (k,\phi(m))=d
    so d=kx+yn

    Let:
    f: r \mapsto r^k
    g:r\mapsto r^x

    \{r_1^k,\hdots,r_n^k\} will form a reduced residue system if and only if no two of them are congruent modulo m , which means that the map
    f: r \mapsto r^k has to be invertible.




    Which means that f(g(r))=g(f(r))=r^{kx}\equiv r^{d-yn}
    f(g(r))=g(f(r)) = r because the map is invertible and f and g are inverses functions of each other
    so r \equiv r^{d-yn}

    r^{d-yn} \equiv r^d * (r^{-1})^{yn} \equiv r^d * 1^y \equiv r^d \mbox{ which needs to be congruent to r }
    Thus, d must be 1.
    (I am a little unsure why the last line must be true)
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Alright, so I gave this a bit of thought and it ends up being a bit harder to prove than I initially thought. You tried reversing the argument I gave, but as you saw it doesn't really work.

    I believe you need the Chinese Remainder Theorem here. I will let you prove the theorem when m=p^\alpha is a prime power. So now suppose the theorem holds when m is a prime power.

    Write m=p_1^{\alpha_1}\hdots p_k^{\alpha_l}. Then n=\phi(m)=\phi(p_1^{\alpha_1})\hdots \phi(p_k^{\alpha_l}).

    Note that, by the CRT, amongst R=\{r_1,...,r_n\}, for every 1 \leq j \leq l, there is a unique subset S_j\subset R containing \phi(p_j^{\alpha_j}) elements which forms a reduced system of residues modulo p_j^{\alpha_j}, such that every x \in S_j is congruent to 1 modulo p_i for i \neq j. Now if R=R^k=\{r^k : r \in R\}, we must also have S_j=S_j^k. Since the theorem holds for prime powers, we must have that (k,\phi(p_j^{\alpha_j}))=1, for every 1 \leq j \leq l. This implies that (k,\phi(p_1^{\alpha_1})\hdots \phi(p_k^{\alpha_l}))=(k,n)=1.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Note that a proof using elementary group theory (Lagrange's theorem) is easy.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof with quadratic residue
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 17th 2011, 03:17 PM
  2. Complete Residue Systems Problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: May 22nd 2010, 04:25 PM
  3. Quadratic Residue Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 24th 2010, 09:32 AM
  4. Primitive roots & Reduced residue system
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: March 4th 2010, 05:51 AM
  5. Reduced residue system modulo m
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 20th 2010, 08:12 PM

Search Tags


/mathhelpforum @mathhelpforum