Results 1 to 2 of 2

Math Help - Help with modulo and congruences

  1. #1
    Newbie
    Joined
    Feb 2007
    Posts
    7

    Help with modulo and congruences

    If a1,a2,...,an is a complete set of residues modulo n and gcd(a,n)=1.
    prove that aa1,aa2,...,aan is also a complete set of residues modulo n

    [Hint: It suffices to show that the number in question are incongruent modulo n.]

    Any ideas?
    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 lyla View Post
    If a1,a2,...,an is a complete set of residues modulo n and gcd(a,n)=1.
    prove that aa1,aa2,...,aan is also a complete set of residues modulo n

    [Hint: It suffices to show that the number in question are incongruent modulo n.]

    Any ideas?
    You use the Pigeonhole principle.

    We assume that
    aa_i=aa_j (mod n)
    Since gcd(a,n)=1 we can cancel preserving the modulos,
    a_i=a_j (mod n)
    Thus the only way these can be congruence to each other if they are only equal to each other.
    Meaning aa_1,aa_2,...,aa_n are all distint.
    And there are "n" of them.
    By Dirichlet's Pigeonhole principle it is some premutation of the set {a_1,...,a_n} (not necessarily in that order).

    (This is exciting for you, is it not, you are about to prove Euler's theorem on Fermat's theorem).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  2. congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 5th 2009, 10:59 AM
  3. More congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 17th 2009, 10:40 PM
  4. congruences
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 7th 2007, 09:14 AM
  5. Congruences modulo p
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2007, 07:25 PM

Search Tags


/mathhelpforum @mathhelpforum