4
$\begingroup$

Find all solutions of $x^2+2x-15\equiv0 \pmod{105}$. Now, I wanted to suggest a proof relying on the algorithm presented in class, and there are some parts where I could use some help or criticism.

First of all, let us write the prime factorization of $105$. Then let us find the solutions of this equation modulo every one of the coprime factors and then let us use the Chinese Remainder Theorem to find the set of solutions inclusive of them all(is that grammatically logical?).

$105=3\cdot 5 \cdot 7$. It is easy to see that $x=0$ is already a solution modulo $3$, $5$, and any integer divisible by 15.

Solutions modulo 3: if $f(x)=x^2+2x-15$ then $f(1)=-12\equiv 0 (3)$. Therefore we get $x\equiv 1(3)$. The algorithm now claims: $x-1|f$ and I get: $x+3$ (and a remainder I am led to believe is irrelevant. Why?). $x+3\equiv 0(3)$ means $x\equiv 3k$. That is, every integer divisible by $3$ is a solution modulo 3. (I could actually be noticed at the very beginning, couldn't it?).

Solutions modulo 5: $f(3)$ happens to be one. (Should I try other $f(x)$ or is dividing by $x-3$ sufficient?) Let us now divide:$f(x)=(x-3)(x-5)$ as I've just discerned. $x-5\equiv 0(5)\iff x\equiv 5k (5)$. (It already seems to me like $x=1$ is no longer an option(?).)

Solutions modulo 7:$f(2)$ is a solution. Dividing by $x-2$, ${f\over x-2}=x+4$. Now $x+4\equiv 0 (7)\iff x\equiv 3 (7)\iff x=7k+3$.

That is the problematic part: I was not guided well enough as for how to find an intersection of sets that fits all subequations(Is that even a term?). I am left with:

$x=3k$, $x=5k$, $x=7k+3$.

How can I find a way to find all integers fulfilling it? I would appreciate your help.

$\endgroup$
4
  • 4
    $\begingroup$ It may be easier to complete the square and note that we are solving $(x+1)^2\equiv 16\pmod{105}$. Then analyze mod $3$, $5$, and $7$. $\endgroup$ Commented Aug 19, 2015 at 20:20
  • $\begingroup$ Have you covered the oft helpful Chinese Remainder Theorem? It is your friend :-) $\endgroup$ Commented Aug 19, 2015 at 20:36
  • $\begingroup$ @AndréNicolas I took it into consideration, but that wouldn't implement the algorithm just acquainted. $\endgroup$
    – Meitar
    Commented Aug 19, 2015 at 20:39
  • 1
    $\begingroup$ The full details are a nuisance to write out, since there are $8$ solutions. $\endgroup$ Commented Aug 19, 2015 at 21:02

2 Answers 2

2
$\begingroup$

To solve the equation modulo $3$:

$$ \begin{align} x^2 + 2x - 15 &\equiv 0 \pmod 3\\ x^2 + 2x &\equiv 0 \pmod 3\\ x(x + 2) &\equiv 0 \pmod 3 \end{align} $$

Therefore $x \equiv 0 \textrm{ or } 1 \pmod 3$. Similarly, working modulo 5, we'll again get $x(x+2) \equiv 0$, so $x \equiv 0 \textrm{ or } 3 \pmod 5$. Finally, in modulo 7, we have:

$$ \begin{align} x^2 + 2x - 15 &\equiv 0 \pmod 7\\ x^2 + 2x - 1 &\equiv 0 \pmod 7\\ x^2 + 2x + 1 &\equiv 2 \pmod 7\\ (x + 1)^2 &\equiv 2 \pmod 7 \end{align} $$

So $x+1 \equiv 3 \textrm{ or } 4 \pmod 7$, which means that $x \equiv 2 \textrm{ or } 3 \pmod 7$.

All of this leads to eight possibilities, for each of which you can use the Chinese Remainder Theorem.


There are eight possibilities because there are two choices for an equivalence modulo $3$, two choices modulo $5$, and two again modulo $7$, so in total we have $2^3=8$. Each set of choices will lead to a result modulo $105$. For instance, suppose we take the following set of equivalences: $$x\equiv0\pmod3\\x\equiv0\pmod5\\x\equiv2\pmod7$$

Then we use the Chinese Remainder Theorem to find $x$: $$x \equiv 0\cdot70 + 0\cdot21 + 2\cdot15 = 30 \pmod{105}$$

You can check that indeed $x=30$ satisfies the initial equation. Now do the same for the seven other combinations of equivalences.

$\endgroup$
7
  • $\begingroup$ Thank you for you answer. I still don't quite get how it becomes eight solutions. Can you help me clarifying? $\endgroup$
    – Meitar
    Commented Aug 19, 2015 at 21:39
  • $\begingroup$ @Meitar I added a further explanation. Does that make more sense? $\endgroup$
    – Théophile
    Commented Aug 20, 2015 at 2:49
  • $\begingroup$ Yes, it hit me eventually, the fact that $2\times 2\times 2 =8$ and that this is what it is all about. $\endgroup$
    – Meitar
    Commented Aug 20, 2015 at 5:35
  • $\begingroup$ Can you tell me why $70$ and not 35? $\endgroup$
    – Meitar
    Commented Aug 20, 2015 at 5:36
  • 1
    $\begingroup$ @Meitar Exactly. So, for example, if you were working with the primes $3$ and $17$, then you'd be doing a calculation of the form $a\cdot34+b\cdot18$ to get a result modulo $51$. $\endgroup$
    – Théophile
    Commented Aug 20, 2015 at 14:43
1
$\begingroup$

When you work in mod 3, you can change the function: $f(x)=x^2+2x-15\equiv x^2+2x(\mod3)\equiv x(x+2)(\mod3)$ From here it's easy to see that two solutions work; one when $x=1(\mod 3)$ and one when $x=0(\mod 3)$. From here you can say that $x=3k$ or $x=3k+1$, for any integer $k$.

Now in mod 5, you can still change the function to $f(x)\equiv x^2+2x\equiv x(x+2)\equiv 0(\mod 5)$ to make you life easier. Now for each solution in mod 3, you'll find two more solutions (two because the equation is quadratic) in mod 5. First you would take $x=3k$ and substitute that into the equation in mod 5, i.e.: $$(3k)(3k+2)\equiv 0(\mod 5)$$ This gives solutions of $k\equiv 0(\mod 5)$ and $k \equiv 1(\mod 5)$; equivalently, $k=5y$ or $k=5y+1$ for any integer $y$. Then substitute this back into the $x=3k$ equation you used originally, to get $x=3(5y)=15y$ and $x=3(5y=1)=15y+3$. Now, both of these are solutions to the equation in mod 5 and mod 3.

You would repeat this process for the other solution in mod 3, and get 4 total solutions for mod 3 and mod 5. Then for each of these four solutions, you would repeat the same process in mod 7, totaling 8 solutions.

The main issue in your original approach is that you tried to address each of the different mods independently, but you have to use your answer to each one to get the answer to the next one, as I showed.

$\endgroup$
1
  • $\begingroup$ Thank you for you answer. I don't understand why I have to go to modulo 3 again if I just started there and arrived at something using it in mod 5. Can you put some light on it? $\endgroup$
    – Meitar
    Commented Aug 19, 2015 at 21:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .