0
$\begingroup$

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..

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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