I was watching the minutephysics video on why quantum computers break encryption, and they brought up that $a^p = mb + 1$, or rather that for any two numbers that may not share factors, one of the numbers raised to a certain power will always equal a multiple of the other number plus one. I was wondering if there was a name for this, and if someone could explain it?
Link: https://youtu.be/lvTqbM5Dq4Q at about 4:50
This is Euler's theorem, which also tells us how to find a $p$ that works -- namely, $p$ can be chosen as the totient of $b$, written $\varphi(b)$: $$ a^{\varphi(b)} \equiv 1 \pmod b \qquad\text{when $a,b$ are coprime} $$
A short proof sketch: When $a$ and $b$ are coprime, Bézout's identity tells us that $a$ is invertible modulo $b$. In other words, the residue class of $a$ is an invertible element of the ring of integers modulo $b$, and is therefore an element of the multiplicative group of integers modulo $b$. Lagrange's theorem now says that $a$ raised to the size of the multiplicative group is the identity, and $\varphi(b)$ is just the size of the multiplicative group modulo $b$.