Question

初等数论设n为整数,证明:(12n+5,9n+4)=1？

Answer 1

我们可以使用辗转相除法来证明：
假设d是(12n+5,9n+4)的一个公因数，即d|(12n+5)且d|(9n+4)。
我们可以将9n+4乘以4，得到36n+16，然后将12n+5乘以3，得到36n+15，然后将两个式子相减，得到：
(12n+5)-(9n+4) = 3n+1
也就是说，3n+1是(12n+5,9n+4)的一个公因数。
然后我们可以将9n+4乘以3，得到27n+12，然后将12n+5乘以2，得到24n+10，然后将两个式子相减，得到：
(9n+4)-(12n+5) = -3n-1
也就是说，-3n-1是(12n+5,9n+4)的一个公因数。
综上所述，(12n+5,9n+4)的所有公因数必然是3n+1和-3n-1的公因数。但是，我们可以发现，当n为任意整数时，3n+1和-3n-1的最大公因数是1，因为它们的差是6n+2，而6n+2可以被2整除，而不能被任何奇数整除。因此，(12n+5,9n+4)的最大公因数为1。
因此，原命题得证。