式の最大公約数 \gcd(2n+1,\ n+3)
着眼点互除法の考え方を文字式に使う。一方から他方の何倍かを引いて、定数にする。
\gcd(a,b)=\gcd(b,\ a-kb)\quad(k\text{ は整数})
連続する2整数 n,\ n+1 は互いに素（\gcd(n,n+1)=\gcd(n,1)=1）。
例題
1
1\le n\le30 の整数 n で、2n+1 と n+3 の最大公約数が5になるものは何個あるか。
解答
\gcd(2n+1,\ n+3)=\gcd(n+3,\ (2n+1)-2(n+3))=\gcd(n+3,\ 5)。
これが5 ⇔ n+3 が5の倍数 ⇔ n\equiv2\pmod5。
n=2,7,12,17,22,27。
（検算：n=7 で \gcd(15,10)=5）
答 6個
これが5 ⇔ n+3 が5の倍数 ⇔ n\equiv2\pmod5。
n=2,7,12,17,22,27。
（検算：n=7 で \gcd(15,10)=5）
答 6個