Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
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. –  André Nicolas Nov 18 '11 at 17:24

2 Answers 2

up vote 2 down vote accepted

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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.