# modular cipher proof

the above is a textbook question I found and believe it is very similar to what I have except n=1 mod p-1 and that remainder 1 is something I dont have in my question...

I am terrible at proofs but I believe this textbook question is almost identical to my question.

My question is this: Let m be prime and x be a positive number strictly smaller than m. Suppose also that k congruent to n(mod m- 1). Prove that x^k congruent to x^n(mod m).

I have sat and thought about it but I dont believe this can be true because if you have say (4 congruent to 8 (mod 5))= (4 congruent 3 mod 5) but if you had (4 congruent to 8 (mod 5-1))= you get 0 congruent to 0 (mod 4) and so x^4 doesnt equal x^3 (unless I messed up somewhere.)

I dont understand 2 things from the textbook proof, perhaps some algerbiac rule I dont know of. Last line, how did they come up with M^n? and lastly, how is M^((p-1)*k)=1^k? what happened to p-1 to make it 1?

-
The $\pmod p$ at the end simply tells us that we are working in the ring of residue classes modulo $p$. The usual rules of exponentiation hold in any commutative ring. See my answer for a listing of the explicit rules used here. –  Jyrki Lahtonen Feb 27 '12 at 9:18
thanks jyrki, i understand what you said, I was basically missing the fact they used fermat's theorem to turn that M^(p-1) into a 1. But how do I prove the question above in bold? –  Raynos Feb 27 '12 at 9:41
I tried to answer the question in bold. I have some trouble reading your above example. Let's do an example here. Let $m=5$. It is a prime, and we have $m-1=4$. For this example let's pick $k=10$ and $n=6$. These are congruent to each other modulo $4$, because $k-n=10-6=4$ is divisible by four. Let's try with $x=2$. Here $x^{10}=2^{10}=1024$ and $x^6=2^6=64.$ We see that $x^k-x^n=1024-64=960$. This is divisible by $m=5$, so the claim holds in this case. –  Jyrki Lahtonen Feb 27 '12 at 10:12

Here $x$ is a non-zero element of the ring $\mathbb{Z}_m$, where $m$ is a prime number. By Little Fermat we have $$x^{m-1}\equiv 1\pmod m.$$ If we have the congruence $n\equiv k\pmod{m-1}$, this means that $n=k+q\cdot(m-1)$ for some integer $q$. Then we have $$x^n=x^{k+q\cdot(m-1)}=x^k\cdot x^{q(m-1)}=x^k\cdot(x^{m-1})^q\equiv x^k\cdot 1^q=x^k\pmod{m},$$ where in the next to last step we used Little Fermat.

Let's check the steps on that line of congruences one at a time. The first congruence claims $$M^n\equiv M^{k\cdot(p-1)+1}.$$ This follows from the fact that $n=k\cdot(p-1)+1$. Whenever raising objects to an integer power makes sense, we have the rule: if $a=b$, then $M^a=M^b$. This step is an application of that rule.

On to the second congruence $$M^{k\cdot(p-1)+1}\equiv (M^{p-1})^k\cdot M^1.$$ This is an application of the hopefully familiar rules of exponentiation: $$x^{a+b}=x^a\cdot x^b$$ and $$(x^m)^n=x^{mn}.$$ Let's work our way from right to left. There the factor $(M^{p-1})^k$ equals $M^{k\cdot(p-1)}$ by an application of the latter rule: $x=M$, $m=p-1$, $n=k$. Then we also apply the former rule with $x=M$, $a=k\cdot(p-1)$, $b=1$. The rule $M^1=M$ is also used.

The next congruence states that $$(M^{p-1})^k\cdot M\equiv 1^k \cdot M.$$ This follows from the principle that if $x=y$, then $x^k=y^k$. Here $x=M^{p-1}$. By Little Fermat that is congruent to 1, so $y=1$. The claimed congruence is gotten from this by multiplying both sides with $M$.

The last congruence states that $$1^k M\equiv M.$$ Well, we always have $1^a=1$ and we also have $1\cdot M=M$, so this is easy.

So this is just a chain of equalities. If you have not seen these before, you may find it a bit confusing that a congruence really is an equality. It becomes a second nature after you familiarize youself with the ring of residue classes modulo $p$. Plenty of resources in the textbooks (as well as in the web) will get you started with congruences.

-

Ok so we know Fermat's little theorem. This basically tells us that when working mod p the powers of something (not divisible by p) cycle round every $p-1$ times. This might not be the minimal length of the cycle.

So what the Lemma is telling you is that as if you have any number $n$ that is congruent to $1$ mod $p-1$ then immediately you know that working mod $p$, the number $a^n$ is going to give you the same thing as $a$. ($a$ not divisible by $p$).

Can you see how this works? It is just using the cyclic nature mentioned above.

Your result is just a generalisation of this fact. It is true.

As for the textbook proof...we are studying what $M^n$ is mod $p$ so we had better start with it. Then they use the fact that $n$ is $1$ more than a multiple of $(p-1)$ to split up the power. Finally they use Fermat's little theorem on the first part of the product.

-