Find number in a certain range satisfying three modulus requirements

381 Views Asked by At

I have to show that $\;x = 37\quad$ is the only number $\;x\in \{n\in \Bbb N: n \le 110\}\text{ that satisfies: }x\equiv 1 \pmod 2,\;x\equiv 2 \pmod 5\qquad$ and $\;x\equiv 4 \pmod {11}.$

By using The Chinese remainder theorem I've found, that:

$$x=55\cdot 1 + 22\cdot 2 + 10\cdot 4 = 139,$$

but $\;139\equiv 29 \pmod {110}.$

What I'm doing wrong?

2

There are 2 best solutions below

10
On

Appplying CRT correctly

I'll address the question of uniqueness, but I see a mistake in how you applied the Chinese Remainder Theorem, so I think that's worth addressing, too. There are different ways to use the CRT. The usual constructive approach is to write:

$$1\cdot 55\cdot n_2 + 2\cdot 22\cdot n_5 + 4\cdot 10\cdot n_{11}$$

where $n_2$ is a multiplicative inverse of $55$, modulo $2$, $n_5$ is a multiplicative inverse of $22$, modulo $5$, and $n_{11}$ is a multiplicative inverse of $10$, modulo $11$. In your solution, these multiplicative inverses appear to be missing, which is why you got an incorrect answer. In this case, we could take $n_2=1$, $n_5=3$, and $n_{11}=-1$. That would lead to the solution:

$$1\cdot 55\cdot 1 + 2\cdot 22\cdot 3 + 4\cdot 10\cdot (-1)=55+132-40=147$$

We have $147\equiv 37\pmod{110}$, so that matches the correct answer.

Uniqueness

Now, what about uniqueness? According to the CRT, as it's usually stated, if we have relatively prime moduli, and if $M$ is the product of those moduli, then our solution will be unique modulo $M$. To verify this, we need to check that $2$, $5$ and $11$ are pairwise coprime, and we need to check that their product is $110$. Both of these are immediate, so we have uniqueness in the desired modulus.

This guarantee of uniqueness comes from the fact that every possible set of remainders modulo $2$ and $5$ and $7$ occurs for some number from $0$ to $109$. There are $110$ possible sets of remainders, so none of them can show up twice in the stated range. These considerations should come up in the proof of CRT, though, and aren't necessary to make every time you apply it.

More efficient application of CRT

As an aside, I don't actually use the CRT that way. A much easier algorithm is this:

We want a number congruent to $4\pmod{11}$, so we start with $4$. If this number is also congruent to $2\pmod5$, great. Else, add $11$ repeatedly until we have a number congruent to $2\pmod{5}$:

$$4+11=15\\ 15+11=26\\ 26+11=37$$

Now, if this number is already congruent to $1\pmod2$, then we're done. Otherwise, we could start adding $55$ repeatedly until we got the desired $\mod2$ congruence. In this case, we're already there.

0
On

$$x=4+11X=2+5Y=1+2Z\Rightarrow11X=-2+5Y=-3+2Z$$ The equation $$2Z-5Y=1$$ admits the solution $(Z,Y)=(18,7)$ then the general solution $$Z=18+5t\\Y=7+2t$$ which comes from $$(2Z-5Y)-(2\cdot18-5\cdot7)=2(Z-18)-5(Y-7)=0$$ For $t=0$ one has $Z=18$ and $Y=7$ which corresponds to $X=\dfrac{-2+5\cdot7}{11}=3$ Thus taking any of the three values, for example $X=3$ we have $$x=4+3\cdot11=37$$

It is easy to verify that since $$4+11X=2+5(7+2t)\iff11X=33+10t$$ in order to have $X$ integer the parameter $t$ should be multiple of $11$ so the next value to be considered is $t=11$ which give $x=147\gt110$. Thus $37$ is the only integer asked.