[SOLVED] Rusty about groups

Printable View

October 15th 2008, 11:21 AM
Moo

[SOLVED] Rusty about groups

Hi !

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

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 ;)
October 15th 2008, 12:15 PM
Opalg

Quote:

Originally Posted by Moo

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

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

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

(Wondering) I never heard of Carmichael's indicator (nor did Google, as far as I can tell).
October 15th 2008, 12:23 PM
Moo

Quote:

Originally Posted by Opalg

$\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 ?

Quote:

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 (Crying)

Quote:

(Wondering) 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 !
October 15th 2008, 12:42 PM
Opalg

Quote:

Originally Posted by Moo

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)$ .
October 15th 2008, 03:35 PM
Laurent

Quote:

Originally Posted by Moo

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).