Thank you!

Now so I know if I didn't do it by brute force, I would have to use the Euclidean algorithm correct? I looked up some sample problems with solutions that is where I am getting messed up on. I am not sure how that plays out. Could you shed some light on that?

The algorithm described in the Wikipedia article involves finding modular inverses, and the typical fast algorithm for this is the extended Euclidean algorithm; also possible is modular exponentiation. For some nice pencil and paper solutions see

this thread.

Here is how your problem plays out, using labels from the

Wikipedia article.

\(\displaystyle \displaystyle x \equiv 5\ (\text{mod}\ 17)\)

\(\displaystyle \displaystyle x \equiv 10\ (\text{mod}\ 16)\)

\(\displaystyle \displaystyle x \equiv 0\ (\text{mod}\ 15)\)

N = 4080

N / 17 = 240

N / 16 = 255

N / 15 = 272

\(\displaystyle \displaystyle e_1\) is (the modular inverse of 240 mod 17) multiplied by (240).

\(\displaystyle \displaystyle e_2\) is (the modular inverse of 255 mod 16) multiplied by (255).

Likewise for \(\displaystyle \displaystyle e_3\).

We find that

\(\displaystyle \displaystyle e_1 = 9\cdot240 = 2160\)

\(\displaystyle \displaystyle e_2 = 15\cdot255 = 3825\)

\(\displaystyle \displaystyle e_3 = 8\cdot272 = 2176\)

So the solution is given by (15)(2160) + (10)(3825) + (0)(2176) \(\displaystyle \displaystyle \equiv\) 90 (mod N).

Note that it wasn't actually necessary to calculate \(\displaystyle \displaystyle e_3\) because it just got multiplied by 0.

To explain modular inverses: The Wikipedia article says "For each

*i* the integers \(\displaystyle n_i\) and

*N* / \(\displaystyle n_i\) are coprime. Using the

extended Euclidean algorithm we can find integers \(\displaystyle r_i\) and \(\displaystyle s_i\) such that \(\displaystyle r_i\)\(\displaystyle n_i\) + \(\displaystyle s_i\)

*N* / \(\displaystyle n_i\) = 1." This means that \(\displaystyle s_i\) multiplied by

*N* / \(\displaystyle n_i\) plus a multiple of \(\displaystyle n_i\) equals 1; in other words, \(\displaystyle s_i\) is the modular inverse of

*N* / \(\displaystyle n_i\) mod \(\displaystyle n_i\).

So for \(\displaystyle \displaystyle e_1\) we need to find the modular inverse of 240 mod 17. This is the same as the modular inverse of 2 mod 17. I'll use simplependulum's method from

this thread:

\(\displaystyle [2^{-1}] = [\frac{1}{2}] = \frac{[9]}{[18]} = [9]\)

Now for the modular inverse of 255 mod 16, which is the modular inverse of 15 mod 16.

\(\displaystyle [15^{-1}] = [\frac{1}{15}] = \frac{[1]}{[-1]} = \frac{[-1]}{[1]} = [-1] = [15]\)