# powers and congruences

• Oct 23rd 2009, 02:05 PM
jimmyjimmyjimmy
powers and congruences
Hi, I don't know how to do math code or anything to make it look good, but bear with me please.

Given integers a and m,
Suppose a^e == 1 mod m (where == is the congruence sign, ^ raises to a power)
Suppose e is the smallest positive integer for which this is true.
If u>0, show that a^u == 1 mod m if and only if e divides u.

It's easy to show that if e divides u, then a^u == 1 mod m.
I am having a hard time showing the other direction though.

One thing I think that might be useful in the proof is to multiply both sides of a^e == 1 mod m by a^(u-e) to obtain a^u == a^(u-e) mod m. If anyone has any hints, please let me know. Thanks.
• Oct 23rd 2009, 02:17 PM
tonio
Quote:

Originally Posted by jimmyjimmyjimmy
Hi, I don't know how to do math code or anything to make it look good, but bear with me please.

Given integers a and m,
Suppose a^e == 1 mod m (where == is the congruence sign, ^ raises to a power)
Suppose e is the smallest positive integer for which this is true.
If u>0, show that a^u == 1 mod m if and only if e divides u.

It's easy to show that if e divides u, then a^u == 1 mod m.
I am having a hard time showing the other direction though.

One thing I think that might be useful in the proof is to multiply both sides of a^e == 1 mod m by a^(u-e) to obtain a^u == a^(u-e) mod m. If anyone has any hints, please let me know. Thanks.

Hint: Euclidean algorithm. Divide u by e with residue: $\displaystyle u =xe + r\,,\,\,with\,\,\,r=0\,\,\,or\,\,\,|r|<e$

now raise a to the u=th power and use minimality of e...

Tonio
• Oct 23rd 2009, 02:23 PM
proscientia
I’m not sure if the Euclidean algorithm works here (but I could be wrong).

Do you know group theory? The problem is very simple if you consider the multiplicative group $\displaystyle \mathbb Z_m^\times$ of the units of the ring $\displaystyle \mathbb Z_m$ of integers modulo $\displaystyle m.$ Then if $\displaystyle e$ is the smallest positive integer such that $\displaystyle a^e\equiv1\pmod m,$ this means $\displaystyle a\in\mathbb Z_m^\times$ has order $\displaystyle e$ in $\displaystyle \mathbb Z_m^\times$ – and the rest is just group theory.
• Oct 23rd 2009, 04:14 PM
tonio
Quote:

Originally Posted by proscientia
I’m not sure if the Euclidean algorithm works here (but I could be wrong).

Do you know group theory? The problem is very simple if you consider the multiplicative group $\displaystyle \mathbb Z_m^\times$ of the units of the ring $\displaystyle \mathbb Z_m$ of integers modulo $\displaystyle m.$ Then if $\displaystyle e$ is the smallest positive integer such that $\displaystyle a^e\equiv1\pmod m,$ this means $\displaystyle a\in\mathbb Z_m^\times$ has order $\displaystyle e$ in $\displaystyle \mathbb Z_m^\times$ – and the rest is just group theory.

$\displaystyle u=xe+r \Longrightarrow 1=a^u=a^{xe+r}=\left(a^e\right)^xa^r=a^r \Longrightarrow r=0$ $\displaystyle by\,\,minimality\,\,of\,\,e\,\,\Longrightarrow e \mid u$ and we're done, and no group theory at all was needed.

Tonio