3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – lulu Mar 20 '16 at 15:51
  • $\begingroup$ 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. $\endgroup$ – BSplitter Feb 8 '18 at 5:47
1
$\begingroup$

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.

for more information see:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.