Use the CRT to give all solutions to:
$$x = 1 \mod 9$$
$$x = 3 \mod 8$$
$$3x = 5 \mod 17$$
Can the standard CRT be used to solve:
$$2x^2 = 5 \mod 9$$
$$x = 13 \mod 21$$
$$2x^2 = 2 \mod 56$$
I'm honestly just confused about the CRT in general. The first one is primarily confusing because the $3x$ appears on the left side of the equation. The second is confusing because I have no idea whether this is possible to solve using the standard method and how we can go about doing that given the $2x^2$s on the left side. I was thinking we might be able to combine $2x^2 = 5 \mod 9$ and $2x^2 = 2 \mod 56$ as $4x^4 = 5*2 \mod 9*56$, but this is honestly just a shot in the dark.
Any help is appreciated.
Answer
Not sure what you mean by the "standard" CRT, but I'll assume it's the way to solve a set of simultaneous congruences of the form
$$x\equiv b_i\pmod{m_i}\ .$$
In this case, for your first example you need to write the third congruence in this form, which can be done as follows:
$$3x\equiv5\pmod{17} \quad\Leftrightarrow\quad 18x\equiv30\pmod{17}
\quad\Leftrightarrow\quad x\equiv13\pmod{17}\ .$$
For your second example you need to do something like this for the first and third congruences, for example
$$\eqalign{
2x^2\equiv5\pmod9\quad
&\Leftrightarrow\quad x^2\equiv7\pmod9\cr
&\Leftrightarrow\quad x\equiv4\ \hbox{or}\ 5\pmod9\ .\cr}$$
So you now have two systems to solve using CRT, and once you simplify the third congruence too, it will most likely be more. Of course it is possible that some of these systems will have no solution.
Once you know the basic method, there are actually a number of short cuts in this example.
No comments:
Post a Comment