1
$\begingroup$

This is a practice problem. Since $5 \cdot 19$ are prime factors of $95$ I tried to break it into two congruence equations and use CRT, but I can't seem to work this out. By Fermat's little theorem we have $3^5 \equiv 3 \pmod 5$, but squaring that multiple times cannot be the solution because then we have to square the RHS of the equation, which is some ridiculous thing. Also $3^{19} \equiv 3 \pmod{19}$, which doesn't help much (I think?) and $3^{18} \equiv 1 \pmod{19}$ which also doesn't help much (I think...). Some help would be appreciated.

  • 0
    Why "least"? Doesn't that number have just one residue mod $N$?2012-10-21
  • 0
    in smallest terms...like instead of 97 mod 95, 2 mod 95. "Least" in that sense2012-10-21
  • 0
    The exponent on the RHS is divisible by 4 ($3^4\equiv 1 \mod 5$). Try dividing the exponent by 18 (long division) and see what happens.2012-10-21
  • 0
    @pootieman: That's the least non-negative integer equivalent to it mod $N$, which is by definition the [residue](http://en.wikipedia.org/wiki/Remainder).2012-10-21

2 Answers 2

2

By Fermat's Theorem (twice) $3^{36}\equiv 1\pmod{95}$. Now we want what $1.1\times 10^{43}$ is congruent to modulo $36$. This big number modulo $4$ is very tame. And modulo $9$, we are looking at $11\times 10^{42}$. Note that $10$ is very nice modulo $9$.

Remark: It is often more efficient to work separately modulo the prime power factors, in this case $5$ and $19$. Modulo $5$, there is no problem, since $3^4\equiv 1\pmod{5}$ and $4$ divides our exponent. So now we examine the exponent modulo $18$. The exponent, modulo $18$, is congruent to $2$. So our power $3^N$ is congruent to $1$ modulo $5$, and to $3^2$ modulo $19$. An easy CRT problem, done by inspection.

  • 0
    @pootieman It is congruent to $0$ and therefore to $2$ mod $2$. And mod $9$, we are looking at $11\times 10^{42}$. But $11$ is congruent to $2$ mod $9$, and $10$ is congruent to $1$ mod $9$, so $10^{42}$ is congruent to $1$ mod $9$.2012-10-21
  • 0
    @pootieman Try long division if you can't think of anything else. The "nice modulo 9" comment, and the fact that 10 is divisible by 2 means that you will quickly get a recurring number with a stable remainder - quite apart from more technical answers which are more generally applicable when the numbers are not so nice.2012-10-21
  • 0
    @pootieman $3^{36}=(3^{18})^2$2012-10-21
  • 2
    @pootieman: In general, our problem about $3^N$ modulo $95$ is reduced to a problem about $N$ modulo $36$, which is a *simpler* problem. One less level of exponentiation.2012-10-21
  • 0
    @AndréNicolas got it, thanks for your insight2012-10-21
0

You can compute $3^{2^n} \text{ mod } 95$ quickly by computing $3^2$, $3^4=(3^2)^2$, $3^8=(3^4)^2$, ...

From that, you can compute $3^n$ by represeting $n$ as a sum of powers of 2 (i.e., $n$'s binary representation). If $n = 2^{k_n} + \ldots + 2^{k_1}$, then $3^n = 3^{2^{k_n}}\cdot\ldots\cdot3^{2^{k_1}}$.

I've whipped up a ruby script to do that computation and get 66. Didn't test much, though, so verify before you use that result for anything important!