一道日本算术奥林匹克竞赛题的数论解法

赵建红

【摘要】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.