Intuitive "proof" of the Euler theorem

258 Views Asked by At

Let $a$ and $n$ be coprime. Then $$a^{\varphi(n)} \equiv 1 \mod n$$

Can you think of an easy, possibly visual, way to justify this theorem without delving into the group theory? In other words, if you were to explain the gist of this theorem to your 12-year-old sibling, how would you do it?

2

There are 2 best solutions below

2
On

The easiest proof relies on $x \mapsto ax$ being a permutation of $U(n)$. That's the proof in Wikipedia.

This proof does not depend on Lagrange's theorem of group theory. It actually provides a simple proof of Lagrange's theorem for all finite abelian groups. Whether this proof can be explained to a child, I don't know.

0
On

For 12 year olds rigorous deductive proofs are difficult I would go inductive. Start with a =2 and n as any prime. Most 12 year old should be able to figure this out .then generalize it to square free composite numbers as n. Then you can extend it to all odd numbers and proceed step by step . Will take some time but nothing difficult.