1

Question: For how many values of b mod 55 does the congruence x^2 + x + b = 0 (mod 55) have exactly 2 solutions? I tried to use quadratic function to solve but really don't get it.

Zhenqing Xu
  • 201

1 Answers1

0

Hint: Given any prime modulus, this equation has exactly $0$, $1$, or $2$ solutions, respectively, based on whether its discriminant, which is $1-4b$, is a quadratic nonresidue (giving $0$), equal to $0$ (giving $1$), or a quadratic residue (giving $2$). The number of solutions it has $\bmod pq$ is simply the product of the number of solutions it has $\bmod p$ and the number of solutions it has $\bmod q$. Can you use this to figure out how many solutions it must have $\bmod p$ and $\bmod q$ and then count from there?

Carl Schildkraut
  • 32,931
  • 1
    No. Put $b=0,1-4b=1^2$. Then the equation has the solution set ${0,10,44,54}\bmod 55$. You are missing the fact that $55$ is composite. – Oscar Lanzi Oct 09 '18 at 00:30
  • 1
    @OscarLanzi Yes, you are correct. I've edited my answer to reflect this. – Carl Schildkraut Oct 09 '18 at 00:35
  • I know for mod 5, if b congruent to 0 or 1 then there is no solution. So for mod 5, does it mean there is 3 values of b to make the congruence have 2 solutions? – Zhenqing Xu Oct 09 '18 at 01:05
  • I can also do the same thing for mod 7 but how can I combine these two consequence together? – Zhenqing Xu Oct 09 '18 at 01:06
  • I actually did not use quadratic formula to solve it. Since in mod 5, x can only congruent to 01234, so I try one by one and find value of b – Zhenqing Xu Oct 09 '18 at 01:07
  • @ZhenqingXu

    1. I think you might have messed up your calculations somewhere - $\bmod 5$, you should get that the solution pairs $(x,b)$ are $$(0,0),(1,3),(2,4),(3,3),(4,0),$$ so it has two solutions iff $b\in{0,3}\bmod 5$ (and has only one solution if $b\equiv 4\bmod 5$).

    2. Try using the Chinese Remainder Theorem.

    3. Since the number $55$ is pretty small, it's feasible to just try all the cases. For larger moduli, this becomes too computationally intensive. I recommend you try to solve it in a method that will apply to the general case.

     – Carl Schildkraut Oct 09 '18 at 02:08