# Number of solutions of the congruence, $x-y \equiv z \pmod{n}$, where $x,y$ in a set contain less than $n$ and relatively prime to $n$?

I know number of solutions of the congruence, $$x+y \equiv z \pmod{n},\tag{1}$$ $x,y\in U_{n}$, is $$N(z)=n\prod_{p\mid n}\left(1-\frac{\varepsilon(p)}{p}\right),$$ where $\varepsilon(p)$ = $\left\{ \begin{array}{l l} 1 & \quad \text{if$p\mid z$}\\ 2 & \quad \text{if$p\nmid z$} \end{array} \right.$

$U_n$ denotes the set of numbers less than $n$ and relatively prime to $n$.

Let $p_{1},p_{2},\cdots ,p_{r}$ be the different prime divisors of $n$, $n=p_{1}^{\alpha_{1}},p_{2}^{\alpha_{2}},\cdots , p_{r}^{\alpha_{r}}$ and $m=p_{1},p_{2},\cdots ,p_{r}$.

If $x$ and $y$ satisfy $(1)$, then $y$ is uniquely determined modulo $n$ bu $x$. So we have find out the number of possible entries for $x$. We partition the interval of integers $[0, n-1]=\{0,1,2,\cdots ,n-1\}$ into the disjoint intervals $I_{k}=[(k-1)m,km-1]$, $k=1,2,3,\cdots , \frac{n}{m}$. By the Chinese Remainder Theorem every integer $x\in I_{k}$ is uniquely determined by its values $x_{i}$ modulo $p_{i},1\leq i\leq r$. i.e. by the congruence $x\equiv x_{i} \mod p_{i},0\leq x_{i}\leq p_{i}-1,1\leq i\leq r$.

$x$in both $I_{k}$ and $U_{n}$, so all $x_{i}$ must be nonzero. There remain $p_{i}-1$ possible choices for $x_{i}$. An additional values for $x_{i}$ has to be ruled out, if $z\equiv z'\mod p_{i},0<z'<p_{i}$. In this case $x_{i}=z'$ would have consequence $y\equiv 0\mod p_{i}$ implying $y\notin U_{n}$. So the number of possible choices for $x$ in both $I_{k}$ and $U_{n}$ to satisfy $(1)$ is $(p_{1}-\varepsilon(p_{1})\cdots (p_{r}-\varepsilon(p_{r})$.

I need to find number of solution of the congruence,

$x-y \equiv z \pmod{n}$, $x,y\in U_{n}$

• – Martin Sleziak Feb 2 '15 at 13:11
• Did you mean to write $\prod_{p\mid n}$ instead of $\prod_{p\backslash n}$? – Martin Sleziak Feb 2 '15 at 13:21
• yes. $\prod_{p\mid n}$. Please give ans – Naveen Feb 2 '15 at 18:28

## 1 Answer

$x\in U_{n} \Leftrightarrow n-x\in U_{n}$

So both $x+y\equiv z \pmod{n}, x,y\in U_{n}$ and $x-y\equiv z \pmod{n}, x, y \in U_{n}$, have same number of solutions.