2022年共通テスト数学ⅠＡの整数問題で出題された1次不定方程式の係数は巨大で、規則性を見つけないと容易には解けないよう設計されていました。本稿ではこの問題で出題された方程式の整数解について考察してみます。
$k^4x-2^4y=1$ の一般解
誘導設問として$$k^4x-2^4y=1 \quad \cdots ①$$という方程式が登場しましたが、実はこれを解くのはそれほど難しくはなく、$k$が奇数の場合、$$(x,y)=\left(16n+1, k^4n+\dfrac{k^4-1}{16}\right)$$という一般解が求められます。ここで$n$は任意の整数です。
なお、$k$が偶数の場合、この方程式は解をもちません（∵$k$が偶数ならば、左辺が偶数、右辺が奇数となり不合理）。
一般解の導出過程はおよそ以下の通りです。
$k$が奇数のとき、$m$を整数として $k \equiv 4m \pm 1$ と表せるので、$$\begin{aligned}
k^{4} &=(4 m \pm 1)^{4} \\
&=\underline{4^{4} m^{4} \pm{ }_{4} \mathrm{C}_{1} 4^{3} m^{3}+{ }_{4} \mathrm{C}_{2} 4^{2} m^{2} \pm { }_{4} \mathrm{C}_{3} 4 m}+1 \\
&=16 M+1
\end{aligned}$$と式変形できます。下線部は$16$の倍数なので適当な整数$M$により$16M$と表せます。これを$①$式に代入すると$$(16M+1)x-16y=1$$ $$\therefore x=16(y-Mx)+1$$という形にできます。ここで$y$は任意の値をとる整数なので、$y-Mx$ という整数は（$x$が含まれていますが）$x$に独立な整数となります。そこで $n \equiv y-Mx$ と置けば$$x=16n+1$$と表せるという寸法です。$y$の値を求めるにはこれを$①$式に代入すればよく、僅かな計算で$$y=k^4n+\dfrac{k^4-1}{16}$$が得られます。
共通テストの場合は $k=5$ だったので、一般解は$$(x,y)=(16n+1,\,625n+39)$$と求められます。
$k^5x-2^5y=1$ の一般解
本問の主眼は指数が$5$に増えた$$k^5x-2^5y=1 \quad \cdots ②$$を解くことです。2022年共通テスト第4問の妙味は、$k^5x-k^8$ が$2^5$で割り切れるという事実を用いる点にあります。これは以下の計算によって正当化されます。
先ほど $k^4=2^4M+1$ であることを導きました。この両辺を2乗すると$$k^8=2^8M^2+2^5M+1$$となりますから、$k^8$を$2^5$で割った余りは$1$と分かります。
また、方程式$②$が成り立っているとすれば、移項により$$k^5x=2^5y+1$$と変形できるので、$k^5x$を$2^5$で割った余りも$1$と分かります。
以上のことから、$k^8$を$2^5$で割った余りと$k^5x$を$2^5$で割った余りが等しいので、その差 $k^5x-k^8$ は$2^5$で割り切れます。いま$k$は一般の奇数なので、$k$が奇数である限り常にこれが成立する訳です。ここが本問のポイントです。
ここから一般解を導きます。
適当な整数$w$を用いて$$k^{5} x-k^{8}=k^{5} 2^{5} w \quad \cdots ③$$と置けるので、$x$について整理すると$$x=k^{3}+32 w$$となります。
ここで、$k^3$を$32$で割った商と余りをそれぞれ$q$、$r$と置いて、$k^3 =32q +r$ と表すことにします。これを$x$の式に代入すると、$$x=32(q+w)+r$$と表せます。
ここで$r$を絶対値最小剰余に限定すれば、$q$と$r$の値が一意に定まります。さらに $n \equiv w+q$ と表すことにすると、$$x=32n+r$$と表せます。このとき$y$は$②$式より、$$2^{5} y =k^{5} x-1$$ $$\begin{aligned} \therefore y &=\dfrac{1}{32}\left\{k^{5}(32 n+r)-1\right\} \\ &=k^{5} n+\dfrac{k^{5} r-1}{32} \end{aligned}$$と求められます。これが方程式$②$の一般解です。
※「絶対値最小剰余」とは、剰余となる整数のうち絶対値が最小となるものを指します。例えば $26=7 \times 3+5$ ですが、絶対値最小剰余による表現では $26=7 \times 4-2$ となります。名称は知らずとも、$\text{mod}$の計算で多用している方は多いと思います。
共通テストの場合は $k=5$ だったので、$5^3$を$32$で割った余りは$29$、つまり $r=-3$ ですから、一般解は$$(x,y)=(32n-3,\,3125n-293)$$と求められます。$②$の整数解のうち、$x$が3桁の正の整数で最小になるのは $n=4$、つまり $x=125$ のときで、$y=12207$ と求められます。
$n=4$ となるような$q$と$w$の組が実際に存在するのか心配になるかもしれませんが、以上の式変形は$w$の存在を保証する$③$式と同値なので必要十分です。
※いま、$q=3$ なので $n=4$ となるためには $w=1$ が必要十分ですが、このとき$③$式より $x=125$ と決まります。また、$x=125$ のとき$③$式より $w=1$ となります。このように、方程式$③$を満たす$w$が存在することと、方程式$②$を満たす$x$が存在することは同値です。
$k^5x-2^5y=1$ の一般解一覧
方程式$$k^5 x-2^5y=1$$の解を $0<k<100$ の範囲について示しておきます。
$k=1\to(32n+1,n)$
$k=3\to(32n-5,243n-38)$
$k=5\to(32n-3,3125n-293)$
$k=7\to(32n-9,16807n-4727)$
$k=9\to(32n-7,59049n-12917)$
$k=11\to(32n-13,161051n-65427)$
$k=13\to(32n-11,371293n-127632)$
$k=15\to(32n+15,759375n+355957)$
$k=17\to(32n-15,1419857n-665558)$
$k=19\to(32n+11,2476099n+851159)$
$k=21\to(32n+13,4084101n+1659166)$
$k=23\to(32n+7,6436343n+1407950)$
$k=25\to(32n+9,9765625n+2746582)$
$k=27\to(32n+3,14348907n+1345210)$
$k=29\to(32n+5,20511149n+3204867)$
$k=31\to(32n-1,28629151n-894661)$
$k=33\to(32n+1,39135393n+1222981)$
$k=35\to(32n-5,52521875n-8206543)$
$k=37\to(32n-3,69343957n-6500996)$
$k=39\to(32n-9,90224199n-25375556)$
$k=41\to(32n-7,115856201n-25343544)$
$k=43\to(32n-13,147008443n-59722180)$
$k=45\to(32n-11,184528125n-63431543)$
$k=47\to(32n+15,229345007n+107505472)$
$k=49\to(32n-15,282475249n-132410273)$
$k=51\to(32n+11,345025251n+118602430)$
$k=53\to(32n+13,418195493n+169891919)$
$k=55\to(32n+7,503284375n+110093457)$
$k=57\to(32n+9,601692057n+169225891)$
$k=59\to(32n+3,714924299n+67024153)$
$k=61\to(32n+5,844596301n+131968172)$
$k=63\to(32n-1,992436543n-31013642)$
$k=65\to(32n+1,1160290625n+36259082)$
$k=67\to(32n-5,1350125107n-210957048)$
$k=69\to(32n-3,1564031349n-146627939)$
$k=71\to(32n-9,1804229351n-507439505)$
$k=73\to(32n-7,2073071593n-453484411)$
$k=75\to(32n-13,2373046875n-964050293)$
$k=77\to(32n-11,2706784157n-930457054)$
$k=79\to(32n+15,3077056399n+1442370187)$
$k=81\to(32n-15,3486784401n-1634430188)$
$k=83\to(32n+11,3939040643n+1354045221)$
$k=85\to(32n+13,4437053125n+1802552832)$
$k=87\to(32n+7,4984209207n+1090295764)$
$k=89\to(32n+9,5584059449n+1570516720)$
$k=91\to(32n+3,6240321451n+585030136)$
$k=93\to(32n+5,6956883693n+1087013077)$
$k=95\to(32n-1,7737809375n-241806543)$
$k=97\to(32n+1,8587340257n+268354383)$
$k=99\to(32n-5,9509900499n-1485921953)$
一般解の式からも分かりますが、$k^px-2^py=1$ という1次方程式の解のオーダーは$p$となります。これは、ある整数解$(x_0,y_0)$が見つかったとして、$$\begin{array}{r}
k^{p} x-2^{p} y=1 \\
-) \quad \quad \quad k^{p} x_{0}-2^{p} y_{0}=1 \\
\overline{k^{p}(x-x_{0})-2^{p}(y-y_{0})=0}
\end{array}$$より、適当な整数$j$により$$\left\{\begin{array}{l}x=2^{p} j+x_{0} \\ y=k^{p} j+y_{0}\end{array}\right.$$と表せることから理解でき、半ば自明と言えます。
$2^5$という係数は $k^4=2^4M+1$ の両辺を2乗して得られる$$k^8=2^8M^2+2^5M+1$$という式から出てきたものです。そう考えると $k^6x-2^6y=1$ など、さらに高次の係数をもつ方程式に拡張するのは工夫が要りそうです。
【参考記事】
11^5x≡１（mod 2^5)
11×３＝３３≡１(mod2^5)
に気づけば
x≡3^5=243≡19(mod2^5)
x=19が解になることは代入して計算すれば確認できる。
martha さん
管理人の pencil です。
コメントありがとうございます。
$11 \times 3 \equiv 1 \pmod{2^5}$ を利用するのは上手い方法だと思います。
これを5乗して$$x \equiv 3^5=243 \equiv 19 \pmod{2^5}$$を導くのは一本取ってやった感がありますね。寧ろ、誘導設問が無ければこのようにして解くのが普通かもしれませんが…。
ところで、この解法は方程式の係数がより高次の冪の場合にも応用可能なところがポイントと言えそうです。例えば6乗の場合は$$11 \times 29=319 \equiv -1 \pmod{2^6}$$から$$11^{6} \times 29^{6} \equiv 1 \pmod{2^6}$$を得るので、$29^{6} \equiv 25 \pmod{2^6}$ から $x=25$ が求められます。実際、これは最小の正の整数解です。
一般に、$n$を正の整数、$k$を奇数とするとき、中国剰余定理から $k \times m=1 \pmod{2^n}$ を満たすような整数$m$が $0 \leqq m \leqq 2^n-1$ の範囲にただ一つ存在することが従います。この事実に基づいて$m$に相当する整数を根気よく探せば、任意の冪乗について本問の方程式を解くことができますね。
ご教示に感謝致します。
方程式$$k^6 x-2^6 y=1$$の整数解は以下の通りです。
$k = 1 \to (64 n+1, n)$
$k = 3 \to (64 n-23, 729 n-262)$
$k = 5 \to (64 n-7, 15625 n-1709)$
$k = 7 \to (64 n-15, 117649 n-27574)$
$k = 9 \to (64 n+17, 531441 n+141164)$
$k = 11 \to (64 n+25, 1771561 n+692016)$
$k = 13 \to (64 n+9, 4826809 n+678770)$
$k = 15 \to (64 n-31, 11390625 n-5517334)$
$k = 17 \to (64 n-31, 24137569 n-11691635)$
$k = 19 \to (64 n+9, 47045881 n+6615827)$
$k = 21 \to (64 n+25, 85766121 n+33502391)$
$k = 23 \to (64 n+17, 148035889 n+39322033)$
$k = 25 \to (64 n-15, 244140625 n-57220459)$
$k = 27 \to (64 n-7, 387420489 n-42374116)$
$k = 29 \to (64 n-23, 594823321 n-213764631)$
$k = 31 \to (64 n+1, 887503681 n+13867245)$
$k = 33 \to (64 n+1, 1291467969 n+20179187)$
$k = 35 \to (64 n-23, 1838265625 n-660626709)$
$k = 37 \to (64 n-7, 2565726409 n-280626326)$
$k = 39 \to (64 n-15, 3518743761 n-824705569)$
$k = 41 \to (64 n+17, 4750104241 n+1261746439)$
$k = 43 \to (64 n+25, 6321363049 n+2469282441)$
$k = 45 \to (64 n+9, 8303765625 n+1167717041)$
$k = 47 \to (64 n-31, 10779215329 n-5221182425)$
$k = 49 \to (64 n-31, 13841287201 n-6704373488)$
$k = 51 \to (64 n+9, 17596287801 n+2474477972)$
$k = 53 \to (64 n+25, 22164361129 n+8657953566)$
$k = 55 \to (64 n+17, 27680640625 n+7352670166)$
$k = 57 \to (64 n-15, 34296447249 n-8038229824)$
$k = 59 \to (64 n-7, 42180533641 n-4613495867)$
$k = 61 \to (64 n-23, 51520374361 n-18515134536)$
$k = 63 \to (64 n+1, 62523502209 n+976929722)$
$k = 65 \to (64 n+1, 75418890625 n+1178420166)$
$k = 67 \to (64 n-23, 90458382169 n-32508481092)$
$k = 69 \to (64 n-7, 107918163081 n-11803549087)$
$k = 71 \to (64 n-15, 128100283921 n-30023504044)$
$k = 73 \to (64 n+17, 151334226289 n+40198153858)$
$k = 75 \to (64 n+25, 177978515625 n+69522857666)$
$k = 77 \to (64 n+9, 208422380089 n+29309397200)$
$k = 79 \to (64 n-31, 243087455521 n-117745486268)$
$k = 81 \to (64 n-31, 282429536481 n-136801806733)$
$k = 83 \to (64 n+9, 326940373369 n+45975990005)$
$k = 85 \to (64 n+25, 377149515625 n+147324029541)$
$k = 87 \to (64 n+17, 433626201009 n+115181959643)$
$k = 89 \to (64 n-15, 496981290961 n-116479990069)$
$k = 91 \to (64 n-7, 567869252041 n-62110699442)$
$k = 93 \to (64 n-23, 646990183449 n-232512097177)$
$k = 95 \to (64 n+1, 735091890625 n+11485810791)$
$k = 97 \to (64 n+1, 832972004929 n+13015187577)$
$k = 99 \to (64 n-23, 941480149401 n-338344428691)$