# Problem about the equivalent proposition about this congruent equation.

Given $c,c',N$, consider the equation $$c'\equiv yc\pmod{N}$$

for some $y$ relative prime to $N$.

In the book I'm reading, it is said that it is equivalent to $$(c',N)=(c,N)=d$$

The necessary direction is easy, and I think in the sufficient direction, we need to prove that in the following numbers:

$$y_0+i\frac{N}{d},i=0,\cdots,d-1$$

there is a number relatively prime to $N$, where $y_0$ satisfies

$$\frac{c'}{d}\equiv y_0\frac{c}{d}\pmod{\frac{N}{d}}$$

My question is why such $i$ exists?

-
Do you already know the existence of multiplicative inverses? I.e. If $\gcd(x, N) = 1$, then there exists $a$ such that $ax=1 \pmod{N}$. –  Calvin Lin Jan 13 '13 at 8:57

## 1 Answer

Hint: Let $c=dx, c'=dx'$, where $x, x'$ are coprime to $N$. As such, $c' = dx' = d(x'x^{-1})x = yc \pmod{N}$. It remains to show that $y=x'x^{-1}$ is coprime to $N$.

-
got it, thank you! –  hxhxhx88 Jan 13 '13 at 9:16