Here is the original problem:(adsbygoogle = window.adsbygoogle || []).push({});

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

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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Number Theory: Calculating mod large number

**Physics Forums | Science Articles, Homework Help, Discussion**