2

I've just been given the following question in my crypto class, and I think I'm fairly sorted for it, but I was just wondering whether there might be any extra solutions to the ones I've worked out.

Compute all solutions of $x^2 + 4x - 21 \equiv 0\,\bmod\,33$

First, I factorised this equation to give $(x + 7)(x - 3)$, which gives me the solutions $-7$ and $3$. However, under the conditions of modular arithmetic, I know that adding or subtracting $33$ as many times as we like will also provide an answer of zero.

IE: Let's try x = 26. $$(26 + 7)(26 - 3) = 33 \times 23 \equiv 0\,\bmod\, 33$$

Thus, it becomes fairly obvious to see that solutions to this equation will take the form $[3]$ and $[26]$, where the square brackets denote congruence classes.

I was given the hint in class that we should try to make the brackets equal to the factors of 33 - IE; try and get to $11 \times 3$, for example. But I really can't see how this would work.

Any further input would be great, thank you!!

Jack
  • 1,074

3 Answers3

2

Hint $ $ By the uniqueness of prime factorizations (or, equivalently, prime $\,p\mid ab\,\Rightarrow\, p\mid a\,$ or $\,p\mid b)$, if $\ p,\, q\ $ are primes, $ $ then $\,\ pq\mid ab\,\iff\ pq\mid a\,$ or $\,\ pq\mid b\ $ or $\ (p\mid a,\ q\mid b)\ $ or $\ (p\mid b,\ q\mid a).\,$ Applying this to your example yields congruences solvable by the Chinese Remainder Theorem.

Bill Dubuque
  • 272,048
1

The general purpose approach to composite moduli is to use the Chinese remainder theorem and Hensel lifting.

That is, you factor the modulus into prime powers, solve the problem modulo each factor, then use the Chinese remainder theorem to reconstitute the result. Since you will probably have two solutions modulo $3$ and two solutions modulo $11$, you will probably have four solutions modulo $33$.

If the individual prime power factors are nontrivial, then you can usually solve the problem modulo the prime, and then use Hensel lifting to extend this to solutions modulo the prime power. But this doesn't apply to your problem, since $3$ and $11$ are already prime.

The hint, I think, is trying to exploit the fact that if $xy = 0 \bmod {33}$, then either:

  • $x = 0 \bmod {33}$
  • $y = 0 \bmod {33}$
  • $x = 0 \bmod 3$ and $y = 0 \bmod 11$
  • $x = 0 \bmod 11$ and $y = 0 \bmod 3$

but in my opinion, it's sort of a weird way to go about the problem.

  • How would I go about utilising the Chinese Remainder Theorem in this context?? – Jack Mar 15 '14 at 11:01
  • If $f(a) = 0 \bmod 3$ and $f(b) = 0 \bmod 11$, then solving the system of equations $c = a \bmod 3$ and $c = b \bmod 11$ will give you a value such that $f(c) = 0\bmod{33}$. –  Mar 15 '14 at 11:04
0

$(x+7)(x-3)\equiv0\mod 33$

Now, as you noticed $ x=-7,3$ are obvious solutions. Also, any number congrunet to $-7$ or $3$ modulo $33$ will be a solution, for instance, $26$, as it is congruent to $-7$ modulo $33$, or $36$, congruent to $3$ modulo $33$.

But there are other possible solutions, congruent to neither $-7$ nor $3$ modulo $33$

If we can solve $x+7=11k$ and $x-3=3k$, for integers $x,k$ then we have a solution, since one of the factors is divisible to $11$ and the other divisible to $3$.

Similarly, we can solve $x+7=3k$ and $x-3=11k$,under the same constraints we have another solution.

Incidentally, both these sets of equations have solutions in integers, namely $15$ and $14$.

Thus all solutions of $x$ must be congruent to one of $-7,3,15,14$ modulo $33$

Guy
  • 8,857
  • 1
  • 28
  • 57
  • Your remark that "one of the factors is congruent to $11$" makes no sense. Probably you meant to say "divisible by $11$". Also, one needs to prove that those $4$ solutions are the only solutions mod $,33.$ Finally, note that if $,x,$ is a root of $,x^2+\color{#c00}4x-21\equiv 0\pmod{33},$ then $,-\color{#c00}4-x,$ is also a root, which halves the root-search effort. – Bill Dubuque Mar 15 '14 at 19:21
  • @BillDubuque I meant divisible yes. but isn't the fact that 11 and 3 are prime proof enough? there can be no other factorization for 33?(with two factors here) – Guy Mar 15 '14 at 19:31
  • That's part of the reason - see my answer. The completeness of the listed solutions does require rigorous proof, not handwaving. Please fix the "congruent to" so that it does not confuse the OP. Please be more careful with your answers. If you are not sure about what you write, then say that, and ask for help. You can learn much that way. – Bill Dubuque Mar 15 '14 at 19:36
  • @BillDubuque yes I fixed that. thank you. – Guy Mar 15 '14 at 19:41