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.

My working so far:

$71-1=70$ and Prime factors of $70$ are $2 \times 5 \times 7$

Check $a=7$:

$7^{(\frac{70}{2})} \equiv 7^{35} \equiv x (mod 71)$

How do I find $x$? Usually I would use Fermat's little theorem and firstly find $\phi(71)$ except 71 is prime (giving the value as $71-1=70$ but this is a fact that we're trying to prove in the first place!!

I could of course use my calculator to calculate it, but this assumes the numbers aren't too extremely horrible.

How else do you calculate this nicely?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

You can use repeated squaring to get to large powers quickly, then use binary to write the exponent as a sum of exponents you've already reached: $$7^1 = 7 \equiv 7\pmod{71}$$ $$7^2 = 49 \equiv 49\pmod{71}$$ $$7^4 = 49^2 \equiv 58\pmod{71}$$ $$7^8 = 58^2 \equiv 27\pmod{71}$$ $$7^{16} = 27^2 \equiv 19\pmod{71}$$ $$7^{32} = 19^2 \equiv 6\pmod{71}$$ $$7^{35}=7^{32}7^27^1\equiv 6\cdot 49\cdot 7\equiv 70\pmod{71}$$ It's still a lot of work, but it's much less than multiplying $7$ by itself $35$ times, even if you reduce mod $71$ each time.

share|improve this answer
    
You can also use simplifications like $7^4 \equiv 58 \equiv -13\pmod{71}$ and then $7^5 = 7 \times 7^4 \equiv -91 \equiv -20\pmod{71}$ and then $7^{35}=(7^5)^7 \equiv -400 \times -400 \times -20\pmod{71}$ –  Mark Bennet Sep 20 '12 at 6:39

Why don't we start with the minimum positive integer that is $>1$ and reach $7^{35}$ as the multiplication by $2$ is much easier.

$2^5=32,2^7=128\equiv -14{\pmod {71}}$

Now $2^8\equiv -28{\pmod {71}},2^{16}\equiv 784\equiv 3,2^{32}\equiv 9$

So, $2^{35}=2^{32}2^3\equiv 9\cdot 8 {\pmod {71}} \equiv 1$

If $m\equiv 2^n{\pmod {71}},$ where $n$ is any positive integer,

$m^{35}=(2^n)^{35}=(2^{35})^n\equiv (1)^n{\pmod {71}}=1$

$\implies (-m)^{35}=m^{35}(-1)^{35}\equiv-1{\pmod {71}}$

$\implies (-m)^5≢1{\pmod {71}}$ and $(-m)^7≢1$

We just need to show that, $(-m)^2 ≢1{\pmod {71}}$

If $n=6,m=64\implies -m=-64\equiv 7{\pmod {71}}$, which is $a$, according to the given problem.

Now $a^2=7^2=49 ≢1{\pmod {71}}$,

so by Lucas test, $71$ is prime.

This method can be employed to any prime of the form $2(2r+1)+1\equiv 3 \pmod 4$

share|improve this answer
    
Yeah I could, it just so happens the question I'm studying asks to choose $a=7$ –  Arvin Sep 22 '12 at 9:33
    
@Arvin, I have also chosen $a=7,$ but the calculation is done with $2$ what is evidently much easier. –  lab bhattacharjee Sep 22 '12 at 10:45

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.