# 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

$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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://math.stackexchange.com/questions/1126474/number-of-solutions-of-the-congruence-x-y-equiv-z-pmodn-where-x-y-in-a", "fetch_time": 1566599015000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-35/segments/1566027319082.81/warc/CC-MAIN-20190823214536-20190824000536-00148.warc.gz", "warc_record_offset": 539246001, "warc_record_length": 31361, "token_count": 857, "char_count": 2150, "score": 3.6875, "int_score": 4, "crawl": "CC-MAIN-2019-35", "snapshot_type": "latest", "language": "en", "language_score": 0.6151089072227478, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00032-of-00064.parquet"}