I'm not great with math so please feel free to correct any mistakes in my question (or add more examples). I'm a software engineer and have recently wanted to better understand the maths behind RSA and Diffie Hellman. The more I learn, the more I get sucked into the wikipedia vortex, and the more this keeps coming up.
Around every corner there seems to be a theorem, formula, or technique where $x \equiv 1\ (\text{mod}\ n)$ is of fundamental importance and I don't understand what property it has that makes it so special (compared to, say, $x \equiv 0\ (\text{mod}\ n)$ or something similar).
For example:
- Fermat's Little Theorem $a^{p-1} \equiv 1\ (\text{mod}\ p)$
- Euler's Theorem $a^{\phi(n)} \equiv 1\ (\text{mod}\ n)$
- Modular Multiplicative Inverse $a\ x \equiv 1 (\text{mod}\ m)$
- Multiplicative Order (the smallest $k$ where $a^k \equiv 1\ (\text{mod}\ n)$)
What's the nature of this equivalency that makes it so pervasive among modular arithmetic and primes? Why don't other equivalencies show up more often like $\equiv 0\ (\text{mod}\ n)$?
Perhaps a new question altogether . . . why isn't it possible to have relative coprimes where there is no $k$ where $a^k \equiv 1\ (\text{mod}\ n)$?
Thanks!!