例題2
3以上9999 以下の奇数aで, a'ーaが10000 で割り切れるものをすべて求め
よ。
解答
a-a=(a-1)a
である。ここで,a-1と aが互いに素であることを, 背理法で証明する。
a-1とaが素数かの公約数をもつと仮定すると
a-1=pb, a=pc (6, cは異なる自然数)
と表されるから, pc-1=a-1 より
pc-1= pb つまり か(c-b)=1
pは素数で2以上であるから, この等式は成り立たず矛盾する。
したがって, a-1とaは互いに素である。(証明終わり)
10000=10=(2-5)*=2*·5
また