2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – Daniel Fischer Jun 26 '13 at 22:26
  • $\begingroup$ 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) $\endgroup$ – chubakueno Jun 26 '13 at 22:31
  • 2
    $\begingroup$ The solutions are of the form $d(nb/d-1)$ for divisors $d\mid b$ and integers $n$. $\endgroup$ – anon Jun 26 '13 at 22:33
  • $\begingroup$ Daniel: Yes!. Chubakueno: Yes!, but I am wondering for all the solutions ! $\endgroup$ – user84040 Jun 26 '13 at 22:35
  • $\begingroup$ Where does this problem come from? $\endgroup$ – lhf Jun 26 '13 at 22:35
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But are these all the solutions? $\endgroup$ – lhf Jun 26 '13 at 22:36
  • 1
    $\begingroup$ Yes. I started out from an arbitrary solution. $\endgroup$ – Berci Jun 26 '13 at 22:37
  • $\begingroup$ wonderful! thanks Berci! $\endgroup$ – user84040 Jun 27 '13 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy