Welcome to our community

Be a part of something great, join today!

Number Theory Eulers phi function, orders, gcd

tda120

New member
Oct 31, 2013
8
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
Mar 10, 2012
834
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
Oct 31, 2013
8
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...