# Why does $\equiv 1\ (\text{mod}\ n)$ seem so important?

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!!

• If $a$ and $n$ are coprime then look at the sequence $\{a,a^2,a^3,\dots\}\pmod n$. As there are only finitely many classes $\pmod n$ these can't all be distinct. Hence we can find $i< j$ with $a^i=a^j\pmod n$. But then $a^{j-i}=1\pmod n$. – lulu Mar 20 '16 at 15:51
• I apologize for answering nearly two years after the question was posed, but I saw this question, and thought I'd chime in. I'm no expert on number theory, but my understanding is that if you have a number $x$ equivalent to 1 (mod $n$), then you can ensure that $x$ is relatively coprime to $n$. This wouldn't occur if $x\equiv 2$ (mod $n$) for instance. One particularly useful theorem is that $x\equiv 1$ (mod $y$) implies that there exist $a,b\in \mathbb{Z}$ such that $ax+by=1$. This is used to prove several other theorems, like perhaps the ones mentioned above. – BSplitter Feb 8 '18 at 5:47

Well I don't have enough rep to comment, otherwise I would have just posted this link to RSA python 3 code in a comment. However, since this is an answer, I'll answer. $p+1≡1\ mod\ p$ is a simple way to express that $p+1 \neq p\ mod\ p$. This might seem obvious, but some pretty cool proofs rely on this, like Euclid's proof of infinite primes. Furthermore, $p-1≡p-1\ mod\ p$ is pretty ugly.