Register to reply 
Number Theory: Calculating mod large number 
Share this thread: 
#1
Mar507, 05:53 PM

P: 1,123

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! 


#2
Mar507, 07:36 PM

HW Helper
PF Gold
P: 2,327

I'm interested in knowing how to tackle this by hand as well!



#3
Mar607, 11:14 AM

Sci Advisor
HW Helper
Thanks
P: 25,244

Well, Euler's theorem got you to 300. But I think you have to walk the rest of the way. Use the power of two idea and just start filling in by squaring the previous entry at each step and reducing mod 341.
3^2 > 9 3^4 > 81 3^8 > ?? 3^16 > ?? 3^32 > ?? Once you have 8 and 32 multiply and reduce and you are done. I don't think thats too bad to do with a calculator. 


#4
Mar607, 11:24 AM

P: 1,123

Number Theory: Calculating mod large number
I was hoping to not have to use a calculator
I also ask because we had an exam a week ago, and we had to do basically the same computation (and it worked out to be 81^2, 81^4, etc, but it was mod 1000, which I thought was a little crazy considering we were not allowed calculators on the exam.) So basically I was just wondering if there was a nice, clever, way to do this. 


#5
Mar607, 11:35 AM

Sci Advisor
HW Helper
Thanks
P: 25,244

That does sound sadistic. What exactly was the question?



#6
Mar607, 11:39 AM

P: 1,123

I was probably missing some clever trick, but even when I asked the professor, he said to use powers of 2, so I don't know.
Here is the original question:  Find the remainder when [tex]3^{56}[/tex] is divided by 1000.  At the time we did not have Euler's Theorem (It probably would not help anyway). We did have fermat's theorem, but that does not apply here (I don't think at least). We basically had just general mod arithmetic. 


#7
Mar607, 12:28 PM

Sci Advisor
HW Helper
Thanks
P: 25,244

I can't think of anything else either. I'll stick with sadistic.



#8
Mar607, 08:32 PM

P: 688

actually, there is a generalized totient function call the Carmichael Function: http://mathworld.wolfram.com/CarmichaelFunction.html
basically [tex]\lambda (340)=LCM(\lambda (11), \lambda (31))=30[/tex] so that, [tex]3^{30}\equiv 1 \mod{341}[/tex] which easily gives, [tex]a \equiv 56 \mod{341}[/tex] the Carmichael Function theorem is in general much stronger than totient function theorem. if you don't like carmichael function, you can always break the modulo into pieces. basically, let [tex]3^{340}\equiv a \mod{341}[/tex] so [tex]3^{340}\equiv a \mod{11}[/tex] and [tex]3^{340}\equiv a \mod{31}[/tex] so [tex]a \equiv 1 \mod{11}[/tex] [tex]a \equiv 25 \mod{31}[/tex] a=11k+1 [tex]11k \equiv 24 \mod{31}[/tex] [tex]k \equiv 5 \mod{31}[/tex] so a=11((31*m)+5)+1 or [tex]a \equiv 56 \mod{341}[/tex] 


#9
May2111, 01:06 PM

P: 11

done by binomial theorem dunno mod theorem
3^56 (3^4)x(3^52) 81x(9^50) 81x[(101)]^50 or 81x[(110)]^50 81x[1+50x10+(50x49x100)/2 +(50x49x48x1000)/6 . . . . . 10^50] from the 3rd term onwards al the trems are divisible by 1000 hence by dividing the first 2 terms by 1000 i wil get the remainder taking 500 common in d first 2 terms [81x(500)x246]/1000 81x246/2 81x123 answer 9963 is it right??? i dnt know modular theory can someone help me wit it?? 


#10
May2111, 08:51 PM

Sci Advisor
HW Helper
Thanks
P: 25,244




Register to reply 
Related Discussions  
Large number  Calculus & Beyond Homework  4  
Computing a large number  Calculus & Beyond Homework  4  
Is ln(1+exp(x)) = x when x is a large number?  General Math  11  
Factoring a large number  General Math  11  
Large number...  Fun, Photos & Games  3 