- #1

- 1,085

- 6

--------------

Use Euler's Theorem to compute the following:

[tex]3^{340} \ \text{mod} \ 341[/tex]

---------------

So Euler's Theorem tells us that if (a,m) = 1, then [tex]a^{\phi(m)} \equiv 1 \ \text{mod} \ m[/tex]

[itex]\phi(341) = \phi(11\cdot 31) = 300[/itex]

OK so now we need to compute [itex]3^{40} \ \text{mod} \ 341[/itex]. And this is where I have a problem.

Basically my problem is that I am trying to do it by hand, and I don't see how to do this easily. Sure I could pull out a calculator, but I don't think that should be necessary. So are there any tips for doing such a calculation? Our instructor suggested that we use powers of 2. Meaning that 40 = 32 + 8 = 2^5 + 2^3. However, this seems kind of ugly given the large moduli for this particular problem. Any ideas? Thanks!