Welcome to our community

Be a part of something great, join today!

Number Theory Euler's theorem for calculating mod

ATroelstein

New member
Jun 30, 2012
15
I am trying to use Euler's theorem for calculating the following:

$$
8^{7} mod 187
$$

I have determined that:

$$
\phi(187) = \phi(11*17) = 160
$$

and

$$
8^{7} = 8^{4} * 8^{2} * 8^{1}
$$

but am unfortunately confused about how to now proceed beyond this point. Thank you.
 

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
I am trying to use Euler's theorem for calculating the following:

$$
8^{7} mod 187
$$

I have determined that:

$$
\phi(187) = \phi(11*17) = 160
$$

and

$$
8^{7} = 8^{4} * 8^{2} * 8^{1}
$$

but am unfortunately confused about how to now proceed beyond this point. Thank you.
I don't think here Euler's theorem can be fruitfully used. But you can use Fermat's little in conjunction with Chinese Remainder to calculate this nicely.

Note that $8^7=2^{21}=x$ (say). Also, $187=11\times 17$. Now by Fermat we have $2^{10}\equiv 1 \pmod{11}$ and $2^{16}\equiv 1\pmod{17}$. These give $x\equiv 2\pmod{11}$ and $x\equiv 32\equiv -2\pmod{17}$. From here it's routine to use the Chinese remainder and get the remainder $x$ leaves mod $187$.
 

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
As I have stated here many times before, I am pathetically lazy, so I look for the easy way out.

First, I start with 82= 64 (mod 187), so we get:

87 = (64)(8)(64)(8)(8) (mod 187)

Next, I calculate 64*8 the old-fashioned way:

(6*8*10) + (4*8) = 480 + 32 = 512.

I'm going to guess that 2 multiples of 187 are all we're going to pack into 512. So:

512 = 512 - 374 = 138 (mod 187).

So 87 = (138)(138)(8) (mod 187).

Did I mention I'm afraid of big numbers? Well, I am. So next I'm going to apply a trick that often works well in modular arithmetic:

Since 138 = -49 (mod 187),

87 = (138)(138)(8) = (-49)(-49)(8) = (49)(49)(8) (mod 187).

Here, I have an unpleasant choice to make: do I tackle 49*49 next, or 49*8?

The small numbers win!

Now 49*8 = (4*8*10) + (9*8) = 320 + 72 = 392. Well, that's pretty close to 374, which makes me happy. So:

87 = (49)(49)(8) = (49)(392) = (49)(18) (mod 187).

I've avoided "hard calculations" as much as possible, but I have no choice but to evaluate 49*18 now:

49*18 = (40+9)(10+8) = 400 + 320 + 90 + 72 = 882.

So I want to know what 882 (mod 187) is. Knowing that 180*5 = 900, I don't think I can get 5 multiples of 187 in 882, so 4 is my best guess:

187*4 = 400 + 320 + 28 = 748. So:

87 = 882 = 882 - 0 = 882 - 748 = 134 (mod 187)

Does this jibe with caffeinemachine's answer?

134 = 132 + 2 = 0 + 2 = 2 = (mod 11). Check.

134 = 119 + 15 = 0 + 15 = 15 = -2 (mod 17). Check.
 

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
I'd like to point out here that caffeinemachine's solution is not so easy to carry out as it might seem.

Given that:

x = 2 (mod 11)
x = -2 (mod 17)

we seek integers k,m such that:

11k + 2 = 17m - 2

or, equivalently:

17m - 11k = 4

If we knew some integers r,s with:

17r - 11s = 1, we could take m = 4r, k = 4s.

Fortunately, the euclidean division algorithm gives us a way to find these two integers r and s:

17 = 11*1 + 6
11 = 6*1 + 5
6 = 5*1 + 1

Therefore:

1 = 6 - 5
5 = 11 - 6
6 = 17 - 11, so:

1 = 6 - 5 = 6 - (11 - 6) = 2*6 - 11 = 2*(17 - 11) - 11 = 2*17 - 3*11, so we have:

r = 2, s = 3, and in turn:

m = 8, k = 12. Hence:

11*12 + 2 = 17*8 - 2, evaluating either side gives us:

134, which is the desired power 87​ (mod 187).
 

johng

Well-known member
MHB Math Helper
Jan 25, 2013
236
Hi,
I tend to agree with caffeinemachine that the easiest computation is via the Chinese remainder theorem.
Given m and n relatively prime, the unique x (mod mn) that satisfies x = a (mod m) and x = b (mod n) is of the form a + km for some k with 0 <= k < n.
(All of the given values are different for the range of k's and so one must be b (mod n)).

So I want -2 + 17k = 2 (mod 11)
6k = 4 (mod 11)
k = 8 (mod 11) -- the multiplicative inverse of 6 is 2 mod 11.
So x = -2 +8*17 = 136 - 2 = 134.
 

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
Hi,
I tend to agree with caffeinemachine that the easiest computation is via the Chinese remainder theorem.
Given m and n relatively prime, the unique x (mod mn) that satisfies x = a (mod m) and x = b (mod n) is of the form a + km for some k with 0 <= k < n.
(All of the given values are different for the range of k's and so one must be b (mod n)).

So I want -2 + 17k = 2 (mod 11)
6k = 4 (mod 11)
k = 8 (mod 11) -- the multiplicative inverse of 6 is 2 mod 11.
So x = -2 +8*17 = 136 - 2 = 134.
Yes, but....

The ease of this is "hidden" in the step:

6k = 4 --> k = 8.

In this particular case, one can guess rather easily that [6-1]11 = 2 by trial-and-error. In general, finding a (multiplicative) inverse mod n (if it exists, which it assuredly will if n is prime, and the element inverted is not a multiple of n = p) involves exactly the same steps I outlined above. One often does not have a discrete log table lying around to read off which power of a generator a particular element is, and one HAS to resort to the division algorithm to find the inverse (finding primitive elements is not always a trivial task, although it IS easier for small numbers).

Don't misunderstand me, I find the application of the CRT a beautiful and elegant solution. At its heart, the CRT states that:

If (m,n) = 1, then $\Bbb Z_{mn} \cong \Bbb Z_m \times \Bbb Z_n$

However, while the ring-homomorphism one way is trivial to display, the inverse homomorphism is nontrivial (and amounts to actually solving the congruence pair). There is a slight difference between knowing a solution exists and exhibiting that solution.

Your calculations and mine are, of course, the same, as can be seen by taking the equation:

11*12 + 2 = 17*8 - 2 (mod 11).

I also do not know if the original poster has seen a PROOF of the CRT, with an understanding of what it means for "compound" moduli. In all fairness (both to you and caffeinemachine) I admit sometimes an understanding of more advanced methods makes problems like these easier to deal with. Do I run the risk of under-estimating the original poster's sophistication? Of course. I am the first to admit the laziest proof is not always the shortest.

If the exponent has been larger, my way would undeniably be more cumbersome. I certainly mean no disrespect to either of your fine answers. Knowing we can reduce an exponent b in ab (mod n), by taking b (mod φ(n)), is something well worth remembering, if one has been exposed to Euler's theorem (which we can assume the OP has, by the thread title), and I note in passing that Fermat's "Little Theorem" (which caffeinemachine DOES invoke) is just a special case of Euler's Theorem.

One hopes that the original poster gains more from our discussion of solution techniques here than just the answer to his problem.
 

johng

Well-known member
MHB Math Helper
Jan 25, 2013
236
Yes, but....

The ease of this is "hidden" in the step:

6k = 4 --> k = 8.

In this particular case, one can guess rather easily that [6-1]11 = 2 by trial-and-error. In general, finding a (multiplicative) inverse mod n (if it exists, which it assuredly will if n is prime, and the element inverted is not a multiple of n = p) involves exactly the same steps I outlined above. One often does not have a discrete log table lying around to read off which power of a generator a particular element is, and one HAS to resort to the division algorithm to find the inverse (finding primitive elements is not always a trivial task, although it IS easier for small numbers).


Given the parameters of the CRT, namely m, n are relatively prime, I'm trying to solve a + mk = b for k. So of course m does have an inverse mod n. Granted, the finding of such inverse requires a little work, but it's not exorbitant. A slight extension of the Euclidean algorithm for gcd's produces x and y with mx + ny = 1, and so x is the inverse of m. I find the extension a bit cumbersome to do by hand, but it's a Programming I exercise to encode (maybe toward the end of the course). Even for large integers, the gcd algorithm is "usually" quite fast; as you probably know the worst case is for consecutive Fibonacci numbers. But even here, it's logarithmic.
 

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
Yes, that is what I was getting at. If the exponent is large-ish (say > 1000 for example), using a gcd algorithm is going to be MUCH faster than direct computation.

But with an exponent of only 7, direct computation can be done straight-forwardly, without involving more abstract results. Is this preferable? It depends on your point of view, I suppose. One thing that CAN be said about your solution/caffeinemachine's solution is that it is more widely applicable to a greater range of problems :)