整数の性質の問題

手順 1：互除法で特殊解を 1 つ見つける

$9$ と $7$ に互除法を用いると
$$9=7\cdot 1+2,7=2\cdot 3+1$$
となり、最大公約数は $1$ です。これを逆にたどります。
$$1=7-2\cdot 3$$
$2=9-7\cdot 1$ を代入すると
$$1=7-(9-7)\cdot 3=7\cdot 4-9\cdot 3$$
よって $9\cdot (-3)+7\cdot 4=1$ となり、$(x,y)=(-3,4)$ は 1 つの解（特殊解）です。

手順 2：もとの式から引いて整理する

$$9x+7y=1$$
$$9\cdot (-3)+7\cdot 4=1$$
辺々引くと $9(x+3)+7(y-4)=0$、すなわち
$$9(x+3)=7(4-y)$$

手順 3：互いに素であることを使う

$9$ と $7$ は互いに素なので、$x+3$ は $7$ の倍数です。$m$ を整数として $x+3=7m$ とおけます。これを代入すると $9\cdot 7m=7(4-y)$ より $4-y=9m$ です。よって整数解はすべて
$$x=7m-3,y=-9m+4(m\text{ は整数})$$
と表されます。

手順 4：指定された形に直す

$0\leqq p\leqq 6$ にするため、$m=k+1$ とおくと
$$x=7(k+1)-3=7k+4,y=-9(k+1)+4=-9k-5$$
となります（$m$ がすべての整数を動くとき、$k$ もすべての整数を動きます）。$p$ は $x$ を $7$ で割った余りなので、$0\leqq p\leqq 6$ を満たす $p$ は $4$ だけであり、このとき $q=-5$ です。

確認：$k=0$ のとき $(x,y)=(4,-5)$ で、$9\cdot 4+7\cdot (-5)=36-35=1$ です。

したがって $(p,q)=(4,-5)$ です。

$9x+7y=1$ の整数解を求める。$x=4,y=-5$ のとき $36-35=1$ となるので特殊解である。よって一般解は $x=4+7k,y=-5-9k$ ($k$ は整数) と表せる。これは $p=4,q=-5$ にあたり、$0\leqq 4\leqq 6$ を満たす。

検算：$9(7k+4)+7(-9k-5)=63k+36-63k-35=1$ となり、確かに成り立つ。

$p$ の一意性：$9x\equiv 1(\mathrm{mod}7)$ より $2x\equiv 1(\mathrm{mod}7)$、つまり $x\equiv 4(\mathrm{mod}7)$ なので、$0\leqq p\leqq 6$ では $p=4$ のみ。このとき $y=(1-9\cdot 4)/7=-5$ なので $q=-5$。