4
$\begingroup$

How do I solve 12x^2 + 28x + 1 mod 35? I tried breaking it into mod 7 and mod 5 but not sure how to proceed from there.

Below is my sketch work:

$12x^2 + 28x + 1 \equiv 0 \mod 35$

$12x^2 + 7x + 1 \equiv 0 \mod 7$

$(3x + 1)(4x + 1) \equiv 0 \mod 7$

$2x^2 + 3x + 1 \equiv 0 \mod 5$

$(2x+1)(x + 1) \equiv 0 \mod 5$

  • 0
    The factorizations are fine, and as shown by @joriki, quickly lead to the answers. You chose the reduction mod $7$ cleverly, obtaining (second displayed line) something that factors by sight. For somewhat larger primes, such clever choices of replacement coefficients might not be easy. There would have been even nicer choices. For example, replace $12$ by $-2$, $28$ by $0$, and $1$ by $8$. We get $-2x^2+8=-2(x-2)(x+2)$. Now the solutions are immediate.2011-11-18

2 Answers 2

2

Your work so far is great. Now you know that one factor in each equation must be $0$. Since $\mathbb F_5$ and $\mathbb F_7$ are fields, each linear factor has exactly one zero. That gives you two possibilities for each of the remainders, and each of the four combinations gives you one possible remainder $\bmod35$. For instance, using the first factor in each equation, $3x+1\equiv0\bmod7$ yields $x=2\bmod7$, and $2x+1\equiv0\bmod5$ yields $x=2\bmod5$. The unique remainder $\bmod35$ with these remainders is $2$, and indeed $12\cdot2^2+28\cdot2+1=48+56+1=105\equiv0\bmod35$.

0

In $12x^2 + 28x + 1 \equiv 0 \mod 35$, since 28 $\equiv -7 \mod 35$ wouldn't it become $12x^2 - 7x + 1 \equiv 0 \mod 35$? Now, couldn't we just solve this in the reals and then take each of the solutions $\mod 35$? For solutions we would get $1\over 3$ and $1\over 4$, which are 12 and 9, respectively (since $3\times 12\equiv 1$ and $4\times 9\equiv 1 \mod 35$). I checked it and this method does produce answers congruent to 0 mod 35 in the original equation.