# find the least positive interger solution

• Jan 13th 2008, 08:53 AM
yellow4321
find the least positive interger solution
.

.
• Jan 15th 2008, 04:18 AM
Opalg
Quote:

Originally Posted by yellow4321
ive been given
x congruent 3mod4
x congruent 13mod33
x congruent 35mod88

i solved to find unique solution = 211 but then it asks for find the least positive integer solution and state the largest modulus for which the solution is unique. i have no clue how to go about this?

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 PM
yellow4321
.

.