Number Theory: Euler's Theorem proofs

[tiny quartz]

Hello, I’ve been trying to understand some proofs of Euler’s theorem more thoroughly, but I’m struggling to grasp a few arguments.

In the first proof of Euler’s Theorem (see first two screenshots), the goal is to create a bijection between the set S holding all units of n and the set $a \cdot S$ holding the products of all elements of S times a. To do so, the division algorithm is used to show that the elements in the latter set are also units mod n. That is, the elements in the set $a \cdot S$ are in S as well. Uniqueness of this mapping is then shown using contradiction. The rest of the argument is straightforward.

The second proof of Euler’s Theorem is much shorter, but I don’t understand why its valid to omit the long explanation of why there’s a bijection between the two sets S and $a \cdot S$. I’m not sure why the gcd(a, n) = 1 implies that multiplication by a is a bijection. Additionally, why does being relatively prime to n imply that the product of all units mod n is invertible?

[dawn swallow]

Parayeet
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[jade patrol]

These two are essentially the same proof. The second one simply omits some details that are considered obvious and are spelled out in the first. The fact that gcd(a,n)=1 is equivalent to a being invertible modulo n follows from Bézout’s identity: if gcd(a,n)=1, then there exist integers k and m such that ak+nm=1.

[tiny quartz]

.solved