 | 中国剰余定理を使うと、示せるようですね。
一般に、整数p,q,rに対して、
gcd(p,q)=gcd(p,r)=1⇔gcd(p,qr)=1
が言えるので、次を示せば十分です。
「すべての正の整数の組(n,k)≠(偶数,奇数)に対して、
gcd(n,a(k-a))=1となるような整数aが存在する。」
（証明）
(ⅰ)nが素数のとき：
a=0,1,・・・,n-1の値の中でn|a(k-a)となるaはa=0,kの高々2個なので、
n＞2ならば、少なくともn-2個のaが適しますし、
n=2ならは、kが偶数であることから、a=1が適します。
(ⅱ)n=(p[1])^(d[1])・・・(p[j])^(d[j])（p[i]は素数）のとき：
すべてのi=1,・・・,jに対して、
a[i](k-a[i])がp[i]の倍数とならないようなa[i]が存在します。
ここで、中国剰余定理により、すべてのiに対して、
a≡a[i]（mod p[i]）となるようなaが存在するので、
a(k-a)≡a[i](k-a[i])（mod p[i]）
すなわち、a(k-a)はどのp[i]でも割り切れず、gcd(n,a(k-a))=1です。
（証明終了）
|