Number Theory: Calculating mod large number

In summary: Then you have to remember about the 3^4 that you factored out. And you have to remember the 500 that you factored out. And you have to remember the 1000 that you factored out. So you should have:3^56=1000*(1+28*(-10)+378*(-100)+. . .)So there is a mistake in the numbers. But your method is clever.
  • #1
mattmns
1,128
6
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!
 
Physics news on Phys.org
  • #2
I'm interested in knowing how to tackle this by hand as well!
 
  • #3
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 that's too bad to do with a calculator.
 
  • #4
I was hoping to not have to use a calculator :smile:

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
That does sound sadistic. What exactly was the question?
 
  • #6
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.
 
Last edited:
  • #7
I can't think of anything else either. I'll stick with sadistic.
 
  • #8
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
done by binomial theorem don't know mod theorem

3^56
(3^4)x(3^52)
81x(9^50)
81x[(10-1)]^50
or
81x[(1-10)]^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
TROGLIO said:
done by binomial theorem don't know mod theorem

3^56
(3^4)x(3^52)
81x(9^50)
81x[(10-1)]^50
or
81x[(1-10)]^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
81x123answer
9963
is it right?
i dnt know modular theory
can someone help me wit it??

That's actually a clever approach. But you don't need to factor the 81 out. And you are making some mistakes with your powers. Just work with 3^56=9^28=(1-10)^28. Now do the binomial expansion. Do it carefully this time. It's (1+x)^28 with x=(-10). You have some signs in the expansion.
 
Last edited:

What is number theory?

Number theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers. It involves the study of patterns and structures within numbers, as well as their properties under various operations.

What is the modulus (mod) operator and how is it used in number theory?

The modulus operator, denoted as %, is a mathematical operation that finds the remainder when one number is divided by another. In number theory, the mod operator is used to calculate the remainder when a large number is divided by another number. This can be useful in solving problems involving divisibility, prime numbers, and congruences.

How do you calculate mod of a large number?

To calculate mod of a large number, first divide the large number by the smaller number. The remainder obtained is the mod value. For example, to find mod 17 of 187, we divide 187 by 17 and get a remainder of 3, therefore the mod value is 3.

What is the significance of calculating mod of a large number?

Calculating mod of a large number is important in number theory as it helps in solving problems related to prime numbers, divisibility, and congruences. It also has applications in cryptography, coding theory, and computer science.

Can mod of a large number be negative?

No, the mod of a large number cannot be negative. The mod operation always results in a non-negative remainder. If the result is negative, the mod value is equal to the absolute value of the remainder plus the divisor. For example, mod -7 of 20 is equal to 13, since (-7 + 20) = 13.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
116
  • General Math
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
648
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Back
Top