Eulers phi function, orders, gcd

In summary, the conversation discusses proving that a^d=1 (mod m) given that a, k, l, and m are integers greater than 1, and a^k=1 (mod m) and a^l=1 (mod m). It is also mentioned that d=gcd(k,l) and that there exists integers x and y such that kx+ly=d. The question asks for clarification on whether k must divide phi(m) and for guidance on how to approach the problem. The response clarifies that it is not necessary for k to divide phi(m) and suggests using the fact that kx+ly=d to solve the problem. It also recommends checking out the LaTeX forum for better readability in future
  • #1
tda1201
8
0
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!
 
Mathematics news on Phys.org
  • #2
tda120 said:
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.
 
  • #3
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...
 

FAQ: Eulers phi function, orders, gcd

What is Euler's phi function?

Euler's phi function, also known as the totient function, is a mathematical function that counts the positive integers up to a given number n that are relatively prime to n. In other words, it returns the number of positive integers less than or equal to n that are coprime to n.

How is Euler's phi function calculated?

Euler's phi function can be calculated using the formula φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk), where p1, p2, ..., pk are the distinct prime factors of n. This formula works because the number of integers less than n that are coprime to n is equal to the number of integers less than n that are not divisible by any of its prime factors.

What is the order of an element in a group?

The order of an element in a group is the smallest positive integer n for which gn = e, where g is the element and e is the identity element of the group. In other words, it is the smallest number of times that the element must be multiplied by itself to get the identity element.

How do you find the order of an element in a group?

The order of an element in a group can be found by repeatedly multiplying the element by itself until the identity element is obtained. The number of multiplications required is the order of the element. If the identity element is not obtained after a certain number of multiplications, the order is considered to be infinite.

What is the relationship between Euler's phi function and the order of an element in a group?

There is a direct relationship between Euler's phi function and the order of an element in a group. Specifically, if g is an element of a group G with order n, then φ(n) = n - 1. This means that the number of positive integers less than n that are coprime to n is equal to the number of elements in G that are not equal to the identity element.

Similar threads

Replies
5
Views
2K
Replies
4
Views
2K
Replies
1
Views
594
Replies
11
Views
1K
Replies
3
Views
1K
Replies
2
Views
1K
Replies
1
Views
2K
Back
Top