1
$\begingroup$

I have already proved that there is a solution, and I have seen many proofs that simply state that there are obviously $\gcd(a, n)$ solutions of the form:

$$x_0, x_0 + \frac{n}{g}, x_0 + \frac{2n}{g}, \dots , x_0 + \frac{(g-1)n}{g}$$

This is not obvious to me though, and have no idea how they arrive at this conclusion.

$\endgroup$
  • $\begingroup$ Do you accept that those are the solutions, and just want to know how one might go about discovering them in the first place, or is it that you do not see how those numbers solve the problem? $\endgroup$ – Arthur May 2 '18 at 20:15
  • $\begingroup$ I don't understand how those solutions were obtained. $\endgroup$ – Missyinvisible May 2 '18 at 21:05
0
$\begingroup$

The equation $ax\equiv b\pmod{n}$, knowing that $g=\gcd(a,n)\mid b$, becomes $$ gAx-gB=kgN $$ where $a=gA$, $n=gN$, $b=gB$. This in turn becomes $$ Ax-B=kN $$ or $Ax\equiv B\pmod{N}$. Note that $\gcd(A,N)=1$, so $A$ is invertible modulo $N$. Thus there exists $C$ with $AC\equiv 1\pmod{N}$ and therefore the equation becomes $x\equiv BC\pmod{N}$. There is a single $x_0$, with $0\le x_0<N$ satisfying this condition.

Clearly, $x_0$ is also a solution to $ax\equiv b\pmod{N}$.

Similarly, there is a single solution $x_1$ satisfying $N\le x_1<2N$, and, more generally, a single solution $x_k$ satisfying $kN\le x_k<(k+1)N$, namely $$ x_k=x_0+kN $$

Note that, for $0\le h<g$ and $0\le k<g$, $x_h\not\equiv x_k\pmod{n}$. Thus we have found exactly $g$ solutions $x_0,x_1,\dots,x_{g-1}$.

Each solution to $ax\equiv b\pmod{n}$ is congruent to one of these modulo $n$.

$\endgroup$
1
$\begingroup$

Since you proved a solution $x_0$ exists (probably by applying Bezout identity) it's easy to see that any other solution is of the following form $$y=x_0+t\frac{n}{g}, t\in\mathbb{Z}$$ Indeed, from $ay\equiv b \pmod{n}$ and $ax_0\equiv b \pmod{n}$ we have $$a(y-x_0)\equiv 0 \pmod{n} \Rightarrow n \mid a(y-x_0) \Rightarrow\\ \exists q\in\mathbb{Z}: a(y-x_0)=nq \overset{\gcd(a,n)=g}{\Rightarrow}\\ a_1g(y-x_0)=n_1gq \Rightarrow a_1(y-x_0)=n_1q \overset{\gcd(a_1,n_1)=1}{\Rightarrow}\\ n_1 \mid y-x_0 \Rightarrow y=x_0+tn_1, t\in\mathbb{Z} \Rightarrow \\ y=x_0+t\frac{n}{g}$$


So, obviously each $x_0 + \frac{n}{g}, x_0 + \frac{2n}{g}, \dots , x_0 + \frac{(g-1)n}{g}$ is also a solution. The remaining part is to show that there are exactly $g$ solutions between $0$ and $n$.

From $0< y \leq n$ ($y=0$ is not a solution, otherwise $n \mid b$) we have $$-x_0< t\frac{n}{g} \leq n-x_0 \iff -gx_0< tn\leq gn-gx_0 \iff \\ -gx_0< t_{\min}\cdot n \leq t\cdot n \leq gn-gx_0 \iff \\ 0\leq (t - t_{\min})n < gn-gx_0+gx_0=gn \iff \\ 0\leq t - t_{\min} < g$$ So, regardless of $t_{\min}$ (e.g. $t_{\min}=0$), this leads to $g$ solutions maximum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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