Number TheoryEulers phi function, orders, gcd

tda120

New member
Let a, k , l , m e Z>1 and let a^k=1 (mod m) and a^l= 1 (mod m).
Let d=gcd(k,l)
Prove that a^d=1 (mod m).

I get already confused at the start: Is it true that k|phi(m) (Lagrange) but k can also be a multiple of the order of a (mod m) and then it can be the other way round.

Can anybody clarify this and give me a direction to start working? Thanks!

caffeinemachine

Well-known member
MHB Math Scholar
Let a, k , l , m e Z>1 and let a^k=1 (mod m) and a^l= 1 (mod m).
Let d=gcd(k,l)
Prove that a^d=1 (mod m).

I get already confused at the start: Is it true that k|phi(m) (Lagrange) but k can also be a multiple of the order of a (mod m) and then it can be the other way round.

Can anybody clarify this and give me a direction to start working? Thanks!
Hey tda120.

No. It is not necessary that $k|\phi(m)$. An easy counterexample is by taking $k=2\phi(m)$.

As for the question, use the fact that there exist integers $x$ and $y$ such that $kx+ly=d$.

I'd like to suggest that you check out our LaTeX forum and learn some basic LaTeX so that you will be able to post more readable questions.

tda120

New member
Thank you, I think this helps me a lot!
You're right; I should start using LaTeX, but I'm still a bit shy at using it...