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.

How do I achieve this result via Pepin's test by using Euler's Theorem and such to simplify $3^{2^{31}}$ and get the desired congruence of 10,324,303?

$3^{(F_5-1)/2} = 3^{2^{31}} = 3^{2,146,483,648} \equiv 10,324,303 ≢ -1 (mod 4,294,967,297)$

Where $F_5$ is Fermat's 6th number $2^{32}+1$

Using powermod functions gives the desired result for $a^{b} mod(m)$ but I'd like to do this one by hand to better understand how powermod simplifies.

Thanks!

share|improve this question
    
Do you really want to calculate it 'by hand'?? What is the real question you want to ask? –  Berci Sep 19 '12 at 17:04
    
If you want to use Euler's Theorem, you will need the factorization of $F_5$ in order to find $\varphi(F_5)$. The factorization is known, but rather goes against the spirit of Pepin's Test. –  André Nicolas Sep 19 '12 at 20:55

1 Answer 1

Firstly, working modulo $4,294,967,297$ is very difficult by hand and unwieldy even for a pocket calculator.

Secondly, the exponent $2,147,483,648$ has only one $1$ when written in binary, which does not lend itself to giving you an enlightening experience of binary exponentiation.

If you really want to try this, start by computing $3^{16}$ which is quite small. Then square the result and reduce modulo $4,294,967,297$. And repeat $26$ times until you reach $3^{2^{31}}$.

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.