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}$


$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.


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.