.

.

Printable View

- Jan 13th 2008, 08:53 AMyellow4321find the least positive interger solution
.

. - Jan 15th 2008, 04:18 AMOpalg
I would start by splitting each modulus into its distinct prime factors. So for example 88 = 8×11. This means that $\displaystyle x\equiv35\pmod{88}$ is equivalent to

$\displaystyle \left\{\begin{array}{l}x\equiv35\pmod{8} \text{ and} \\ x\equiv35\pmod{11}.\end{array}\right.$

But $\displaystyle 35\equiv3\pmod{8}$, and $\displaystyle 35\equiv2\pmod{11}$.

So the congruence $\displaystyle x\equiv35\pmod{88}$ is equivalent to the two congruences

$\displaystyle x\equiv3\pmod{8}$,

$\displaystyle x\equiv2\pmod{11}$.

In the same way, 33 = 3×11, and you can check that the congruence $\displaystyle x\equiv13\pmod{33}$ is equivalent to the two congruences

$\displaystyle x\equiv1\pmod{3}$,

$\displaystyle x\equiv2\pmod{11}$.

So instead of the three original congruences

$\displaystyle x\equiv3\pmod{4}$,

$\displaystyle x\equiv13\pmod{33}$,

$\displaystyle x\equiv35\pmod{88}$,

we now have five congruences , namely

$\displaystyle x\equiv3\pmod{4}$,

$\displaystyle x\equiv3\pmod{8}$,

$\displaystyle x\equiv1\pmod{3}$,

$\displaystyle x\equiv2\pmod{11}$,

$\displaystyle x\equiv2\pmod{11}$.

But one of these occurs twice, so we can delete the duplicated one. Also, $\displaystyle x\equiv3\pmod{8}$ implies $\displaystyle x\equiv3\pmod{4}$, so we only need to keep the first of these. Thus we're back to a set of just three congruences:

$\displaystyle x\equiv3\pmod{8}$,

$\displaystyle x\equiv1\pmod{3}$,

$\displaystyle x\equiv2\pmod{11}$.

The advantage of doing this is that we now have a system in which each modulus is (a power of) a different prime. This means that we can use the Chinese remainder theorem to complete the solution. This tells you for a start that the "largest modulus for which the solution is unique" is the product 8×3×11=264.

To find the solution, start by combining the first two of these three congruences. We want a number that leaves a remainder 3 when divided by 8, and a remainder 1 when divided by 3. These numbers are small enough that you should soon be able to find the solution 19. Since 3×8=24, this tells us that the first two congruences are equivalent to $\displaystyle x\equiv19\pmod{24}$.

Finally, bring in the third congruence, $\displaystyle x\equiv2\pmod{11}$. Together with $\displaystyle x\equiv19\pmod{24}$, this tells us to look for a number that leaves a remainder 19 when divided by 24, and a remainder 2 when divided by 11. This is slightly more laborious, but can still be done easily enough by mental arithmetic. Start with 19, and add multiples of 24 until you reach a number that leaves a remainder 2 when divided by 11. You get 19, 43, 67, 91, ... . If you keep tabs on the remainders when you divide these numbers by 11, you'll see that they form an obvious pattern: 8, 10, 1, 3, 5, 7, 9, 0,**2**. That points to the one you're looking for! It is the unique solution (mod264). - Jan 15th 2008, 12:52 PMyellow4321
.

.