2
$\begingroup$

I'm stuck on a homework problem and I'm hoping to get a hint in the right direction.

Assuming that $a\perp b$ ($a$ coprime with $b$), I would like to show that for all integers $n$, there is a nonzero integer $k$ so that $a+bk\perp n$.


I started by writing the ideal $(a+bk,n)=\{ax+bkx+ny : x,y\in\mathbb{Z}\}$, hoping to find a $k$ so that $(a+bk,n)=(1)=\mathbb{Z}$. If $a\perp n$, then setting $k=0$ works. However, I had no luck finding such a $k$ when $a\not\perp n$. (This doesn't work. See Brian's comment.)

  • 0
    Even if $a\perp n$, you can’t set $k=0$, since the problem asks for a **non-zero** integer $k$.2012-03-02

3 Answers 3

2

Hint $\rm\ \ Let\ \ k\: =\: a^{\phi(n)}-1 $

3

HINT: Let $P$ be the set of distinct prime factors of $n$. Let $P_0=\{p\in P:p\nmid a\}$. Let $k=\prod P_0$.

2

Hint $\rm\ \ (a+bx,n) = 1\iff a+bx\not\equiv 0\pmod{p}\ $ for all primes $\rm\:p\ |\ n.\:$ This is easy to solve:

$\rm\qquad\ \ \ if\ \ a\not\equiv 0\ \ then\ \ x\equiv 0\:\Rightarrow\: a+bx\equiv\ a\ \not\equiv 0$

$\rm\qquad\ \ \ if\ \ a\equiv 0\ \ then\ \ x\not\equiv 0\:\Rightarrow\: a+bx\equiv bx\not\equiv 0\ \ (else\ \ b\equiv 0\ \Rightarrow\ p\ |\ a,b\ \Rightarrow\Leftarrow\ (a,b) = 1)$

So it works to choose $\rm\: x\:$ such that $\rm\: p\ |\ x\iff p\nmid a,\:$ for all primes $\rm\:p\ |\ n$.