# Finding order with Fermat's little theorem and calculating a power mod $11$.

Fermat's Little Theorem: If $a$ is an integer, $p$ is a prime number and $a$ is not divisible by $p$ then $a^{p-1}\equiv1\mod p$.

order = smallest natural number $d$ such that $a^d\equiv1 \mod m$

1) How can I use this to find the order of $7$ modulo $59$?

2) How can I find the smallest $a\geq0$ such that $a\equiv7^{83}$ (mod $11$) ? im not sure what they mean here, but I think the theorem gives $7^{10}\equiv1$ (mod $11$) so maybe $(7^{10})^8\times7^3\equiv7^3$ (mod $11$) or something? I dont know if thats correct tho..

For the first part of your question.

the little Fermat states that: $7^{58}\equiv1$ by this you know that the order of 7 is a divisor of 58 (this is an easy exercise and quite handy to know). So you have the possibilities ($58=2*29$) $2,29,58$. You just have to check the former two as you already know the last one by the little fermat. As for how to efficiently do the calculation for 29 I can't seem to find a good way, if I do I will edit this post.

For the second part: if you consider $a \ \text{mod} \ b$ there always exists a smallest integer $\geq 0$ which satisfies this. One can show that this integer $c$ satisfies $0\leq c < b$.

I hope this helps

slin0

A quick way to determine whether $7^{29} \equiv 1 \pmod{59}$ or not is to use Quadratic Reciprocity.

See here and here to learn the basics.

We just need to calculate $$\left( \frac{7}{59} \right)$$

By a well-known theorem, we have $$\left( \frac{7}{59} \right) \cdot \left( \frac{59}{7} \right) = (-1)^{\frac{7-1}{2} \cdot \frac{59-1}{2}} = (-1)^{3\cdot 29} = -1$$ We already know that $$\left( \frac{59}{7} \right) = \left( \frac{3}{7} \right) = -1$$

So we have $$\left( \frac{7}{59} \right)=1$$ Therefore, there must be a $x$ such that $$x^2 \equiv 7 \pmod{59}$$ So we have $$7^{29} \equiv x^{58} \equiv 1 \pmod{59}$$ by Fermat's Little Theorem.

This gives the order of $7$ modulo $59$ equal to $29$.

• I didnt quite understand the (59/7) = (3/7) = -1 and (7/59)=1 part. – eyy321 Nov 29 '15 at 10:45
• This notation is the Legendre's symbol. I will explain more later, but you should try searching it first. – Gyumin Roh Nov 29 '15 at 10:47
• I added the wikipedia link. – Gyumin Roh Nov 29 '15 at 13:04