一道日本算術奧林匹克競賽題的數論解法

趙建紅

【摘要】2011年日本算術奧林匹克競賽題中有一道題目看上去非常簡單，但是要做出結果卻不那么容易，本文用初等數論中的整除性將其解出.

【關鍵詞】數論；整除性；奧林匹克；數學競賽

一、原題重現

有一個將1～6各使用1次的六位數，將其叫作A，將A的最高位的數字移動到最低位后得到的新六位數叫作B（例如，A是123 456，B是234 561）；將B的最高位的數字移動到最低位后得到的新六位數叫作C；將C的最高位的數字移動到最低位后得到的新六位數叫作D；將D的最高位的數字移動到最低位后得到的新六位數叫作E；將E的最高位的數字移動到最低位后得到的新六位數叫作F；如果A，B，C，D，E，F分別是2，3，4，5，6，7的倍數，請求出A.

二、分析及相關引理

引理1 一個整數a能被2整除的充要條件是a的末位數能被2整除，即末位數必為0，2，4，6，8之一.

引理2 一個整數a能被3整除的充要條件是a的各位數字之和能被3整除.

引理3 一個整數a能被4整除的充要條件是a的末尾兩位數能被4整除.

引理4 一個整數a能被5整除的充要條件是a的末位數能被5整除，即末位數必為0，5之一.

引理5 一個整數a能被6整除的充要條件是a能同時被2和3整除，即末位數為0，2，4，6，8之一，且各位數字之和能被3整除.

引理6 一個正整數a能被7整除的充要條件是a的奇位數字之和與偶位數字之和的差能被7整除.

引理7 一個整數a能被7整除的充分條件是：若a的個位數字截去，再從余下的數中，減去個位數的2倍，如果差是7的倍數，則a能被7整除.

三、解 答

解 令X=a11a12a13a14a15a16a21a22a23a24a25a26a31a32a33a34a35a36a41a42a43a44a45a46a51a52a53a54a55a56a61a62a63a64a65a66，

則A=（a11，a12，a13，a14，a15，a16），B=（a21，a22，a23，a24，a25，a26）……由題A，B，C，D，E，F的得來方式，可將X化為：

X1=a26a36a46a56a66a16a36a46a56a66a16a26a46a56a66a16a26a36a56a66a16a26a36a46a66a16a26a36a46a56a16a26a36a46a56a66 .

又由于A，B，C，D，E，F分別被2，3，4，5，6，7整除，故可得：

由D能被5整除可得a46=5，由于A，C，E能被2，4，6整除，說明a16，a36，a56末位數都是偶數，即a16∈{2，4，6}，a36∈{2，4，6}，a56∈{2，4，6}，a16，a36，a56互不相等，且能被4整除，要求末尾兩位數能被4整除，故10×a26+a36∈{12，16，24，32，36，52，56，64}，由于a16，a36，a56是偶數，故a26必為奇數，排除偶數后10×a26+a36∈{12，16，32，36，52，56}，進一步，由于D的末位數是5，故排除a26=5的情形后，10×a26+a36∈{12，16，32，36}，將這4個數依次代入.又由于a26，a66末位數都是奇數，一旦確定a26，a66也就隨即可以確定.剩余2個偶數分別用試算法驗證a16，a56代入后所得的F（也即最后一行的數）能否被7整除即可.經驗證最后得：

X=325416254163541632416325163254632541 .

于是，A=325 416.解畢.

【參考文獻】

[1]朱萍.初等數論及其在信息科學中的應用[M].北京：清華大學出版社，2010：20-61.

[2]Joseph H Silverman.數論概論（原書第3版）[M].孫智偉，等譯.北京：機械工業出版社，2008：32-43.