いくつか補足をば。

このアルゴリズムの正当性を説明するには、次の補題が必要です。

補題
p を 5 以上の素数とする。
任意の木には、3 の倍数でも p の倍数でもない数が含まれる。

証明
T を木とし、3 の倍数でない数 b∈T を任意に取る。
b が p の倍数でなければ示すことはない。
b が p の倍数であるとき、
奇数になるまで b を 2 で割って得られる奇数を b' とおくと
3b'+1∈T であり、3b'+1 は 3 の倍数でも p の倍数でもない。□


上で書いた例を元に、
n=7 でどのように証明ができるのかをざっと説明します。

T を木とし、3 の倍数でも 7 の倍数でもない b∈T を任意に取る。
b は mod 21 で B1,B2 のいずれかに含まれる。
B1 であれば Z/7Z の全ての数を構成できる。
B2 であれば Z/7Z の 0 以外の全ての数を構成できる。

b∈B2 のときは、b は mod 63 で C1,C2,C3 のいずれかに含まれる。
C1,C2 であれば、B1 に含まれる数を構成できる。

b∈C3 のときは、b は mod 189 で D1 に含まれる。
よって C1 または C2 に含まれる数を構成できる。

大体こんな流れです。


あと、特定の k のみについて検証したければ
(1)の出力を k が含まれるグループのみにして下さい。