Proving k divides Euler's totient function using group theory

kohb
Messages
2
Reaction score
0

Homework Statement


a > 1, k > 0. Show that k divides \phi(a^k - 1), where \phi is Euler's totient function (Hint: use some group theory).


Homework Equations


If n = p_1^{a_1}p_2^{a_2}...p_m^{a_m}, then \phi(n) = n(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_m)


The Attempt at a Solution


I guess that I need somehow use the fact that \phi(n) is an order of multiplicative group U(Z/nZ), but I don't see how.

Any suggestions are appreciated!
Thanks!
 
Physics news on Phys.org
Guys, does anyone have any ideas how to do it?
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'

Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'

Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
View full post »

Similar threads

Proving 2 as a Primitive Root of Z_83: A Step-by-Step Approach
Replies
4
Views
2K
Prove if ##a\cdot c = b \cdot c## then ##a = b## using Peano postulates
Replies
2
Views
1K
What is the Proof for the Summation of Integers using Euler's Phi Function?
Replies
1
Views
2K
Proving that Aut(K), where K is cyclic, is abelian
Replies
5
Views
2K
RSA encryption in the real world?
Replies
2
Views
2K
I Dfns group action & group, written in terms of the other
Replies
26
Views
489
Prove Euler's Totient Function: Divisibility of phi((2^n)-1) by n
Replies
1
Views
3K
Probability problem (counting numbers which are not divisible by ##k##
Replies
3
Views
2K
Finding 2 solutions of this Bessel's function using a power series
Replies
8
Views
2K
Proving Divisibility Using Fermat's Theorem
Replies
4
Views
3K

Hot Threads

Recent Insights

Back
Top