- #1
mattmns
- 1,128
- 6
Here is the original problem:
--------------
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!
--------------
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!