2

I've been asked to calculate $3^{12000027}\pmod{35}$ without the use of a calculator. I'm new to modular arithmetic, so I searched for the possible approaches to this problem. The fastest way I could find is the right-to-left binary method described here. I've implemented this algorithm in a program to evaluate how many iterations it would take, which turns out to be $24$. The number $12000027$ is not prime, so Fermat's Little Theorem doesn't appear to be applicable.

Is there some other trick that can be applied for this particular number, or is there really no faster way to determine the solution? It seems like an unnecessary amount of manual labour.

Jack D'Aurizio
  • 353,855
Overv
  • 177
  • 1
  • 6
  • @DanielFischer Unfortunately not, but I've just started reading up on it. Does Euler's extension make it applicable to (some) composites? – Overv Sep 30 '16 at 13:53
  • The exponent isn't what needs to be prime, it's the modulus. You can use the Chinese remainder theorem and compute the remainders modulo $5$ and $7$ separately, or you can use Euler's extension of Fermat's theorem, $a^{\varphi(n)} \equiv 1 \pmod{m}$ if $\gcd(a,m) = 1$. – Daniel Fischer Sep 30 '16 at 13:54
  • @DanielFischer That is very helpful, I think I know enough to do it now :) – Overv Sep 30 '16 at 13:56

2 Answers2

2

You may exploit the Chinese remainder theorem and Fermat's little theorem. In order to compute $N=3^{12000027}$ $\pmod{35}$, it is enough to compute $N\!\pmod{5}$ and $N\!\pmod{7}$. Since $3,5,7$ are mutually coprime, $$ 3^{4n}\equiv 1\pmod{5},\qquad 3^{6m}\equiv 1\pmod{7} $$ and since $$ 12000027\equiv 3\pmod{4},\qquad 12000027\equiv 3\pmod{6} $$ we have: $$ 3^{12000027}\equiv 3^3\equiv \color{red}{27}\pmod{35}. $$

Jack D'Aurizio
  • 353,855
0

Suppose $r$ is the remainder when $3^{12000027}$ is divided by $35$.

Hence $0\leq r\leq 35$ and $3^{12000027}\equiv r \pmod {35}$

Now $\gcd\ (3,35)=1$. Hence by Euler's theorem, $$3^{\phi(35)}\equiv 1\pmod {35} $$

But ${\phi(35)}={\phi(5.7)}=35.(1-\frac{1}{5})(1-\frac{1}{7})=35.(\frac{4}{5}) (\frac{6}{7})=24$

Then $$3^{24}\equiv 1 \pmod {35}\\ \therefore (3^{24})^{500001}\equiv 1 \pmod {35}\\ \therefore (3^{24})^{500001}.3^3\equiv 1.\ 3^3 \pmod {35}\\ \therefore 3^{12000027}\equiv 27\pmod {35}$$

Hence $r=27$.

vbm
  • 632