Euler Phi Function

561 = 3 × 11 × 17. Calculate φ(561). Every prime that divides φ(561) also divides 560 = 24 × 5 × 7, which is what φ(561) would be if 561 were prime. In fact (Z/561)∗ has no element of order 32: deduce that a^560 ≡ 1 mod 561 for every a ∈ Z coprime to 561 even though 561 is not prime.

Solution:
φ(561) = 320. But 320 = 64 × 5. Since there is no element of (Z/561)∗ of order 32, every element is of order dividing 16 × 5 and therefore dividing 560. So a^560 = 1 in (Z/561)∗.

---

Can someone explain the solution please?

Split the solution into separate logical steps:

φ(561) = 320.
But 320 = 64 × 5.
There is no element of (Z/561)∗ of order 32.
So every element is of order dividing 16 × 5.
So the order of every element is dividing 560.
So a^560 = 1 in (Z/561)∗.

Which of these steps don't you understand?

φ(561) = 320.
But 320 = 64 × 5.
There is no element of (Z/561)∗ of order 32.
---

I don't understand from here.

So every element is of order dividing 16 × 5.

So the order of every element is dividing 560.
So a^560 = 1 in (Z/561)∗.

(Z/561)* is a group of order Phi(561) = 320. So every element has order dividing 320 = 64 x 5.

Suppose there's an element whose g whose order o(g) doesn't divide 16 x 5.
Then o(g) must be one of 32, 64, 5x32 or 5x64.
But then one of g, g^2, g^5, g^10 will have order 32, contradicting what we were told.

I assume you can follow the last 2 steps below: they are easy.