What is the difference between $\bmod{p - 1}$ and $\bmod p$

Question

I have a doubt in my research work, can anyone tell me;

• What is the difference between $\bmod {p-1}$ and $\bmod p$

Answer 1

• If we assume that $p$ is prime then $\bmod p$ is forming the field $Z/pZ$ or denoted by, $Z_p$ or $\mathbb{F}_p$. Indeed $\mathbb{F}_p$ is a finite field.

• If $p$ is not a prime then $\bmod p$ is not a field.

• If $p$ is a prime then $\bmod p-1$ is prime only if $p=3$ then $p-1 = 2$ which is the only even prime number.

• if $p$ is a prime then $p-1$ is the order of the multiplicative abelian group formed by the non-zero elements $\mathbb{F}_p^*$.

Answer 2

Both $(p-1)$ and $p$ play a role in a decryption scheme. Let's say you want to find values $e$ and $d$ to the decryption equation:

$$ (x^e)^d = x\ (mod\ p)$$

Then, you should solve the equation: $$ed = 1 \pmod {p-1}$$

If you find such $e$ and $d$, then $ x^{ed} $ would equal to:

$$ x^{1 + k(p-1) } = x^{1} (x^{(p-1)})^k \pmod p $$

The second term on the right is equal to $1$ by Fermat's Little Theorem. In other words, the product of the exponents must be $1$ bigger than a multiple of $(p-1)$.

So, in summary, the decryption operation is in $\Bbb Z^*_p$, but the inverse calculation is in $\Bbb Z^*_{p-1}$.

Furthermore, note that there are p+1 integer numbers between 0 and p inclusive. If we consider all integers under the addition operations $\pmod p$, such group $\Bbb Z_p$ will have p elements: $0, 1,\ldots, p-1.$ An inverse of $x$ would be $-x$.

But, if we consider those numbers under multiplication, then to have a group we must get rid of $0$, because $0$ would not have an inverse. We are left with numbers $1,2,\ldots,p-1$. This list has $p-1$ numbers, and this is the order (size) of the multiplicative group $\Bbb Z^*_p$. The $*$ means that the zero was removed.