# number theory equation involving GCD

Fix the natural number $b$. How can I solve ? $$x+\gcd(x,b) \equiv 0 \mod(b)$$ Can anyone please give me a reference? Best

• Am I understanding correctly: For a fixed (but arbitrary) $b \in \mathbb{N}$, you are looking for all $x \in \mathbb{Z}$ such that $x + \gcd (x,b) \equiv 0 \pmod{b}$? – Daniel Fischer Jun 26 '13 at 22:26
• would $x=b-1$ when $b \ge 1$ count as a solution? Or do you want ALL solutions? (You would have to prove this as unique or investigate the other possible solutions) – chubakueno Jun 26 '13 at 22:31
• The solutions are of the form $d(nb/d-1)$ for divisors $d\mid b$ and integers $n$. – anon Jun 26 '13 at 22:33
• Daniel: Yes!. Chubakueno: Yes!, but I am wondering for all the solutions ! – user84040 Jun 26 '13 at 22:35
• Where does this problem come from? – lhf Jun 26 '13 at 22:35

Let $x=cd$ where $d=\gcd(x,b)$, and let $a:=b/d$. Then we have $\gcd(a,c)=1$, and $$cd+d\equiv 0 \pmod{ad}$$ so that $c+1\equiv 0\pmod a$.
It means, that for each divisor $d$ of $b$, we can choose $c:\equiv -1\pmod{b/d}$, then $x:=cd$ will be a solution, as $c\equiv -1\pmod{a}$ already implies $\gcd(a,c)=1$ hence $\gcd(b,x)=d$.