Question

Find the last 3 digits of 7^12341.
I know that the last 3 digits are 7^12341 (mod10^3)
but I can't see how to figure that out

Answer 1

As a start : find \(\large \phi(10^3)\)

Answer 2

next use the euler theorem and reduce :
\[\large a^{\phi(n)} \equiv 1 \pmod n\]

Answer 3

Notice that \(\large \gcd(7,10^3)=1\) allowing you to use euler thm

Answer 4

oh so we do need Euler's? I read a bit about it but couldn't remember my prof going over it. Was sick one day though....okay.

Answer 5

you familiar with Fermat little theorem ?

Answer 6

O_O

Answer 7

Not really, most advanced I can recall is Hensella's Lemma

Answer 8

ahh then forget about euler and fermat,
you can use Hensel's lemma along with chinese remainder theorem

Answer 9

oh? Could you explain how?

Answer 10

split it into two congruences :

7^12341 (mod 2^3)
7^12341 (mod 5^3)

Answer 11

what does Hensel's lemma tell you ?

Answer 12

tells you how to find a solution to the polynomial P(x) such that it is congruent to 0 (modp^n) where p is prime

Answer 13

midterm on thursday, he wanted this section on it so he rushed through both chinese remainder theorem and Hensel's lemma

Answer 14

Alright, so you want to solve below first
7^12341 (mod 2)
7^12341 (mod 5)

is it ?

Answer 15

since 7 is odd, 7^12341 (mod 2) will be 1
for mod 5....I believe I have that 7^12341 (mod 5) is congruent with 7 (mod 5) right? which is just 2 (mod 5)

Answer 16

or did I get your question confused....

Answer 17

yes how do you work mod 2^3 having known mod 2 ?
let me confess, i haven't learned hensel's lemma in my number theory..

Answer 18

actually 7^12341 (mod 2^3) is straightforward as 7 = -1 mod 8 :

7^12341 = (-1)^12341 = 7 mod 2^3

Answer 19

thats the thing though, Hensel's lemma only applies to solving polynomials that are set to be congruent to 0 modulo a prime to a power

Answer 20

if we know how to find 7^12341(mod 5^3) , we can use chinese remainder thm and conclude

Answer 21

I see you got the right answer there, but I don't know how you knew to use that it was 7 mod 8 and not say 5 or 3 or 1

Answer 22

(-1)^(odd number) = -1 = 7 (mod 8)

Answer 23

oh jeeze, had nothing to do with the modulo 2 thing okay

Answer 24

yeah we need to figure out how to reduce something mod prime power... i have been skipping this topic from months.. :o

Answer 25

lol, let me reread CRT, I suspect thats what is needed.

Answer 26

we can apply CRT only after reducing 7^12341 (mod 5^3)

Answer 27

isn't there a unnamed theorem about a^n = a (mod b) if a and b are relatively prime?

Answer 28

thats the euler theorem which we don't want to use : \(a^{\phi(n)} \equiv 1 \pmod n\)

Answer 29

Alright, read a bit ahead trying to solve this. Probably remembering it from there.

Answer 30

Might just end up skipping this and asking a friend in my class tomorrow. If I do I will post how to do it on here tomorrow for those interested.

Answer 31

Okay good luck with rest of the preparation :)
here is a way to work it using euler theorem :
\[\large \phi(10^3) = \phi(2^3)\phi(5^3) = (4)(100) = 400\]

\[\large 7^{12341} \equiv 7^{400\times 30 + 341}\equiv 7^{341} \pmod {1000}\]

Answer 32

you can reduce 7^341 as follows :
7^2 = 49
7^4 = 49*49 = 401
7^8 = 401*401 = 801
7^16 = 801*801 = 601
7^32 = 601*601 = 201
...
7^256 = 601

7^341 = 7^(256 + 64 + 16 + 4 + 1 ) = 601*401*601*401*7 (mod 1000) = 007

Answer 33

which is indeed a special number to have as last 3 digits,
but im sure there must be more efficient way... do let me know when you find it :)

Answer 34

see
http://math.stackexchange.com/questions/983926/last-3-digits-of-712341

Answer 35

The way my professor intended this question to be completed was through CRT and looking at (mod8) and (mod 125).
mod 8 has an easy pattern to see
7^1 is congruent to 7 which is congruent to -1 (mod 8)
7^2 is congruent to 1 (mod 8)
Therefore 7^12341 follow the pattern of odd powers of 7 and is congruent to 7 (mod 8)
(mod 125) is tougher, and you need to do 10 powers of 7 to get the pattern. I have a test tomorrow and cannot spend the time to write these guys out but it suffices to say that there is a pattern that appears at 7^10 as 7^10 is congruent to -1.
Using this pattern we can determine that 7^12341 is congruent to 7 (mod 125)
From the CRT we get that 7^12341 is congruent to 7 (mod 1000) thus the last 3 digits of 7^12341 is 007.
@ganeshie8 sorry it was a bit late, been busy studying for the test.

Answer 36

basically you're looking for what power of 7 gives you a 1 or -1 and using it to reduce. Nice :)