powers and congruences

**jimmyjimmyjimmy** · October 23rd 2009, 02:05 PM

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.

**tonio** · October 23rd 2009, 02:17 PM

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: $u =xe + r\,,\,\,with\,\,\,r=0\,\,\,or\,\,\,|r|<e$

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

Tonio

**proscientia** · October 23rd 2009, 02:23 PM

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 $\mathbb Z_m^\times$ of the units of the ring $\mathbb Z_m$ of integers modulo $m.$ Then if $e$ is the smallest positive integer such that $a^e\equiv1\pmod m,$ this means $a\in\mathbb Z_m^\times$ has order $e$ in $\mathbb Z_m^\times$ – and the rest is just group theory.

**tonio** · October 23rd 2009, 04:14 PM

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 $\mathbb Z_m^\times$ of the units of the ring $\mathbb Z_m$ of integers modulo $m.$ Then if $e$ is the smallest positive integer such that $a^e\equiv1\pmod m,$ this means $a\in\mathbb Z_m^\times$ has order $e$ in $\mathbb Z_m^\times$ – and the rest is just group theory.

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

Tonio

Thread: powers and congruences

LinkBack

Thread Tools

Display

powers and congruences

Similar Math Help Forum Discussions

Congruences, Powers, and Euler's Formula

Congruences, Powers, and Euler's Theorem

Some congruences

Congruences

congruences

Search Tags