Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can we use Fermat's Little Theorm to find the least non-negative residue modulo m with numbers with large exponents. For example, how would one find the least non-negative residue modulo m with values $n = 3^{1000000}$ and $m = 19$.

I understand how the basic method works (ie finding a way to introduce a factor of $3^{18}$ and then reducing), but dividing 1000000 by 18 is time consuming and I feel there is a quicker method that I don't understand yet.

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

In fact, finding the remainder of $10^6$ by $18$ is not really that tough

Observe that $10^{n+1}-10=10(10^n-1)$ is divisible by $10\cdot 9=90,$ as $9\mid(10^n-1)$ for $n\ge1$

Hence $18\mid(10^{n+1}-10)\implies 10^{n+1}\equiv10\pmod{18}$ for $n\ge1$

So, $$3^{10^n}\equiv3^{10}\pmod {19} \text{ for } n\ge1$$

share|improve this answer
    
As $(a-b)\mid(a^n-b^n)$ where $a,b,n$ are positive integers, $(10-1)\mid(10^n-1)$ –  lab bhattacharjee Feb 10 '13 at 6:41
    
How did you jump from mod 18 to mod 19, that's the step I don't really understand. –  Math_Illiterate Feb 10 '13 at 7:33
    
@Ockham, for prime $p$ and $(x,p)=1,$ if $a\equiv b\pmod {p-1},$ i.e., $a=c(p-1)+b$ for some integer $c, x^a=x^{c(p-1)+b}=(x^{p-1})^c\cdot x^b\equiv x^b\pmod p$ as $x^{p-1}\equiv1\pmod p$ –  lab bhattacharjee Feb 10 '13 at 8:41
add comment

$$3^{18}\equiv 1 \text{ mod 19}$$ $$3^{18*55555}\equiv 1 \text{ mod 19}$$ $$3^{999990}\equiv 1\text{ mod 19}$$ $$3^{1000000}\equiv 3^{10} \text{ mod 19}$$ $$3^{1000000}\equiv 16\text{ mod 19}$$

share|improve this answer
    
can you explain a little more about what you did at each step? –  Math_Illiterate Feb 10 '13 at 6:28
1  
$a^b\equiv c\implies (a^b)^d\equiv c^d \implies a^{bd}\equiv c^d,$ not $a^{b^d}\equiv c^d$ –  lab bhattacharjee Feb 10 '13 at 6:28
    
So the steps listed above are not correct? –  Math_Illiterate Feb 10 '13 at 6:31
    
I don't think this result is correct. According to wolfram alpha $3^{10^6} \equiv 7 \space \text{mod} \space 19$ does not hold. –  Math_Illiterate Feb 10 '13 at 6:44
    
@Ockham I fixed it, sorry for errors. –  Ethan Feb 10 '13 at 6:58
show 2 more comments

Hint $\rm\ mod\ 9\!:\, 10^6\equiv 1^6\equiv 1,\,\ mod\ 2\!:\, 10^6\equiv 0,\ $ so $\rm\ mod\ 18\!:\, 10^6\equiv 10,\,$ so $\rm\,mod\ 19\!:\ 3^{10^6}\!\equiv 3^{10}$

Alternatively $ $ we may employ Euler's Criterion and quadratic reciprocity:

$$\rm\quad mod\ 19\!:\,\ \color{#C00}{3^9} \equiv \left(\frac{3}{19}\right) \equiv\, -\left(\frac{19}{3}\right)\equiv\, -\left(\frac{1}{3}\right)\equiv\,\color{#C00}{-1}$$

$\rm 10^6\!-1 = 9k,\ k\ odd,\,$ so $\rm\, mod\ 19\!:\ 3^{10^6} = 3^{1+9k} =\, 3 (\color{#C00}{3^9})^k\equiv 3 (\color{#C00}{-1})^k\equiv -3$

share|improve this answer
    
I assume your using some theorem that allows you to multiply mod values, can you tell me the name of the theorem or give a little explanation as to how this whole thing works –  Math_Illiterate Feb 10 '13 at 6:40
    
$\rm mod\ 9\!: 10^6\equiv 1,\:$ so $\rm\:mod\ 18\!: 10^6\equiv 1\ \ or\ \ 1+9=10.\:$ Since $\rm\,10^6\,$ is even, it must be $10.\:$ Generally one can use CRT (Chinese Remainder), but that'd be overkill here. –  Math Gems Feb 10 '13 at 6:50
    
@MathGems It was overkill once you started adding colors lol –  Ethan Feb 10 '13 at 7:16
    
@Ethan The colors greatly aid the reader to follow the structure of the inferences. E.g. when I wrote equational inferences like above in older systems without such highlight capabilities, I often received questions, e.g. why is the penultimate congruence true? With it and its source both highlighted in red, one easily sees that it is an application of the replacement rule $\rm\: a\equiv b\:\Rightarrow\:f(a)\equiv f(b),\:$ where $\rm\:f(n) = 3n^k,\:$ and $\rm\,a= 3^9,\,b= -1.\ \ $ In more complex proofs, this structure may be much less clear. –  Math Gems Feb 10 '13 at 16:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.