Saturday, 22 November 2025

Exercise (3.3).17

Show that the equation 

$$n (a + b) x ≡ [a^2− b^2] \pmod {(a + b)}$$

has solutions.

How many solutions does this equation have?


For the equation to have solutions we need $g= \gcd((a+b), n(a+b))$ to divide $[a^2 - b^2]$.

We have

$$ \begin{align} g & = \gcd(a+b, n(a+b) \\ \\ & = \left | (a+b) \right | \times \gcd(n,1) \\ \\ &= \left | (a+b) \right | \end{align}$$

Since $[a^2 - b^2] = (a+b)(a-b)$, we can see that $g \mid [a^2 - b^2]$ and so the equation does have solutions.

The number of incongruent solutions is the gcd $g$, which is $\left | (a+b) \right |$.