Euler's theorem for calculating mod

[ATroelstein]

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]

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]

As I have stated here many times before, I am pathetically lazy, so I look for the easy way out.

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

8⁷ = (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 8⁷ = (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),

8⁷ = (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:

8⁷ = (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:

8⁷ = 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]

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 8⁷​ (mod 187).

 

[johng1]

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]

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]₁₁ = 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 a^b (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.

 

[johng1]

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]₁₁ = 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]

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 :)