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

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

• What is the difference between $$\bmod {p-1}$$ and $$\bmod p$$
• If $p$ is prime, then $p-1$ is the order of the field's multiplicative subgroup. – Ken Goss Jan 17 '19 at 17:29
• @KenGoss Please refrain from answering questions in the comments. Comments should be use to make suggestions or ask for clarifications. – Ella Rose Jan 17 '19 at 19:05

• 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^*$$.

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.