.

.

Printable View

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

. - January 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 is equivalent to

But , and .

So the congruence is equivalent to the two congruences

,

.

In the same way, 33 = 3×11, and you can check that the congruence is equivalent to the two congruences

,

.

So instead of the three original congruences

,

,

,

we now have five congruences , namely

,

,

,

,

.

But one of these occurs twice, so we can delete the duplicated one. Also, implies , so we only need to keep the first of these. Thus we're back to a set of just three congruences:

,

,

.

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 .

Finally, bring in the third congruence, . Together with , 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). - January 15th 2008, 12:52 PMyellow4321
.

.