Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

enter image description here

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?

share|improve this question
    
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

2 Answers 2

up vote 0 down vote accepted

Addressing the question in bold.

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.


My original answer below


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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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