Question

求二元一次方程的整数解

关于x,y的方程:by-ax=1(a,b互素)
求:该方程的整数解.
or:证明符合题设形式的方程不存在整数解.

Answer 1

主要就是应用费马小定理:如果a,b互素，那么a^(b-1) ≡１（mod b）.
即a^(b-1)=kb+1.在将方程改为-ax=-by+1.两式比较得
x=-a^(b-2),y=-(a^(b-1)-1)/b.

Answer 2

有解，假如给定了a,b的值的话，可以代入算出一组特解 （x0,y0） 也就是by0-ax0=1
那么就有无数组解 x=x0+bt,y=y0+at t为任意整数 所以才有无数组解
你代入一下就是 b(y0+at)-a(x0+bt)=by0-ax0=1满足题意

实际上对于ax+by=c二元一次不定方程 如果c为a与b的最小公约数的倍数时,一定有解,并且有无数组解
反之,无解 (我这里讲的所有有解指的是整数解)

Answer 3

辗转相除法，a=bq1+r1……。或费马小定理