Results 1 to 5 of 5

Math Help - [SOLVED] Rusty about groups

  1. #1
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6

    [SOLVED] Rusty about groups

    Hi !

    I've just learnt today that I studied a big part of group theory last year

    So I have two questions that I knew the answer, but forgot it...

    1/ Is the order of an element in \mathbb{Z}/n \mathbb{Z} an integer between m : 1 \leqslant m \leqslant n, or 1 < m < n, or 1 \leqslant m \leqslant \varphi(n), or 1<m \leqslant \varphi(n) ?

    2/ How to prove that if a \wedge n=1, there is a unique m \leqslant n (or <n, depending on the answer of the first question :P) such that a^m \equiv 1 (\bmod n) ?

    And here is an extra question :

    3/ Basically, what's the difference between Carmichael's indicator and Euler's totient function ?


    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Moo View Post
    1/ Is the order of an element in \mathbb{Z}/n \mathbb{Z} an integer between m : 1 \leqslant m \leqslant n, or 1 < m < n, or 1 \leqslant m \leqslant \varphi(n), or 1<m \leqslant \varphi(n) ?
    \mathbb{Z}/n \mathbb{Z} is the additive group of integers mod n. So the element 1 has order n (that's the number of times you must add 1 to itself in order to get a multiple of n). Also, the order of 0 is 1. So the first of those four choices is the correct one.

    Quote Originally Posted by Moo View Post
    2/ How to prove that if a \wedge n=1, there is a unique m \leqslant n (or <n, depending on the answer of the first question :P) such that a^m \equiv 1 (\bmod n) ?
    That is not true. Euler's theorem tells you that a^{\phi(n)}\equiv 1\!\!\pmod{n}. But this number is not unique. For example, if n=10 and a=3 then 3^4\equiv1\!\!\pmod{10}, but also 3^8\equiv1\!\!\pmod{10}.

    Quote Originally Posted by Moo View Post
    3/ Basically, what's the difference between Carmichael's indicator and Euler's totient function ?
    I never heard of Carmichael's indicator (nor did Google, as far as I can tell).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Opalg View Post
    \mathbb{Z}/n \mathbb{Z} is the additive group of integers mod n. So the element 1 has order n (that's the number of times you must add 1 to itself in order to get a multiple of n). Also, the order of 0 is 1. So the first of those four choices is the correct one.
    Hmmm ok !
    And what if it is the multiplicative group ?

    That is not true. Euler's theorem tells you that a^{\phi(n)}\equiv 1\!\!\pmod{n}. But this number is not unique. For example, if n=10 and a=3 then 3^4\equiv1\!\!\pmod{10}, but also 3^8\equiv1\!\!\pmod{10}.
    Oh, right

    I never heard of Carmichael's indicator (nor did Google, as far as I can tell).
    Uuuh I don't know... The paper was talking about \lambda(n)
    If I see this friend again, I'll ask again =)

    Thanks !
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Moo View Post
    And what if it is the multiplicative group ?
    Well, \mathbb{Z}/n \mathbb{Z} is not a group under multiplication mod n (0 doesn't have an inverse, nor does any number that is not coprime to n). However, the set of all elements in \mathbb{Z}/n \mathbb{Z} that are coprime to n does form a group under multiplication mod n. That group has order \phi(n).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Moo View Post
    3/ Basically, what's the difference between Carmichael's indicator and Euler's totient function ?
    Carmichael function is the smallest integer \lambda(n) such that, for every x with x\wedge n=1, x^{\lambda(n)}\equiv 1\ ({\rm mod }\,n). This property is satisfied by Euler's totient function, but it is not always the smallest solution.

    In other words, Carmichael function is the lowest common multiple of the orders of the elements of (\mathbb{Z}/n\mathbb{Z})^*. While Euler's totient function is the cardinality of this group. So that \lambda(n)|\varphi(n). They're equal if n is prime.

    For this and more, I suggest you to have a look at the "Cours d'algèbre" by Michel Demazure, edition Cassini. You'll find it in any university library (in France), it is really well written, with plenty of nice properties and proofs (It is somewhat oriented towards algorithmic applications: primality testing, coding theory).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. bit rusty on partial derivatives
    Posted in the Calculus Forum
    Replies: 6
    Last Post: August 20th 2010, 08:22 AM
  2. PDE trouble - I'm a little rusty
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: August 8th 2010, 06:51 AM
  3. Rusty on my math
    Posted in the Algebra Forum
    Replies: 5
    Last Post: August 27th 2009, 07:43 PM
  4. Bit rusty on my log rearranging
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 12th 2009, 07:43 AM
  5. Replies: 1
    Last Post: February 26th 2009, 10:51 AM

Search Tags


/mathhelpforum @mathhelpforum