1次不定方程式

　2つの数列 の共通項を考えてみます。
数列 {5n}: 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, …
数列 {8n}: 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, …
この2つの数列の共通項は，5 と 8 の公倍数ですから， 40 の倍数です。5 と 8 は互いに素ですから 5 × 8 が最小公倍数となります。

{6n}: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, …
{8n}: 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, …
6 と 8 の最小公倍数は，6 × 8 になりません。 最大公約数が 2 だからです。 この2つの数列の共通項は 24 の倍数になります。

　7x - 4y = 1 を満たす整数の組 (x, y) を求めてみましょう。 このような問題を 1次不定方程式を解く　 ディオファントス方程式を解く　といいます。 7x = 4y + 1 ですから，次の2つの数列の共通項を求めることと同じです。
数列 {7n}: 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, …
数列 {4n+1}: 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, …
したがって，(x, y) = (3, 5) は解の一つです。

　7x - 4y = 0 を満たす整数の組 (x, y) は， 7 と 4 は互いに素ですから，k を任意の整数として， (x, y) = (4k, 7k) となります。
　7x - 4y = 1 の解は，k を任意の整数として， (x, y) = (3 + 4k, 5 + 7k) となります。

　不定方程式 7x - 9y = 1 を解くことは， 数列 {9n + 1} の項で7 の倍数を見つける ことに他なりません。 この数列は初項 10, 公差 9 の等差数列です。 この数列の 7 で割った余りの数列を見てみます。 このことを，7 を法としてみる(modulo 7) と呼ぶことにします。
{9n+1} (mod 7): 3, 5, 0, 2, 4, 6, 1, 3, 5, 0, …
(x, y) = (4, 3) は解の一つであることがわかります。
数列 {9n} を 7 を法としてみると　第7項 で初めて 0 となります。
初項から第6項まではすべて異なりますので， 鳩の巣原理により 1から6まですべてが現れることがわかります。 よって，{9n + 1} を 7 を法としてみると， 初項から第7項までの間に必ず0 から 6 までが出現します。 したがって，遅くても第7項までで解が見つかります。
また，数列 {9n + 1} を 7 を法としてみると， 公差は 2 の等差数列です。 これは，9 を7 で割った余りが 2 だからです。

　不定方程式 45x + 32y = 1 … ① を解いてみます。 数列 {45n + 1} の項で32 の倍数を見つければよいことになります。
{45n+1} (mod 32): 14, 27, 8, 21, 2, 15, 28, 9, 22, 3, …
手間がかかりそうです。 ただ，第32項まで調べればよいので，手間をかければ答えが見つかるという安心感はあります。
この数列は公差が 13 の等差数列なので， 不定方程式 13x + 32y = 1 … ② を解くことと同じです。 これは数列 {32n + 1} の項で 13 の倍数を見つければよいのです。
{32n+1} (mod 13): 7, 0, 6, 12, 5, …
と，すぐに (x, y) = (5, -2) がみつかります。

　② の解から ① の解を求めることができます。 実際，
45x + 32y = (32 + 13)x + 32y = 13x + 32 (x + y) なので，
(x, y) = (5, -7) は 45x + 32y = 1 を満たします。

　表を用いると手順が整理できます。

a	b	q	r	x	y	ax + by = d
45	32	1	13	5	-7	225 + 32y = 1
32	13	2	6	-2	5	-64 + 13y = 1
13	6	2	1	1	-2	13 + 6y = 1
6	1	6	0	0	1	0 + y = 1

よって，
45・5 + 32・(-7) = 1
一般解は，
(x, y) = (5 + 32k, -7, -45k) (k は任意の整数)
ユークリッドの互除法の「商」を活用しているといえます。