账号
密码
注册账号需要审核
您当前的位置:首页 >> 教育新闻

数论问题中同余性质的应用

编辑:中国教育品牌网  发布时间:2018-11-26 14:08:01 

我在做题的时候遇到了这样一道题:设a=10的10的10次方(指数为10的10次方),问某星期一后的第a天是星期几?

对于这种问经过多少天是星期几的问题,实则就是问经过的天数(也就是本题中的a )被7除求余数的问题,也就是有关同余的问题。

首先我们先来明确一下有关同余的概念和基本性质(解决本题只需用一个性质):设m是正整数,若用m去除整数a, b,所得余数相同,则称a与b关于模m同余,记作a≡b(mod m )。例如,34≡4(mod 15)。性质:若a≡b(mod m),则a的n次方与b的n次方关于模m 同余,且ak≡bk(mod m )。(k为整数)

解:由于10≡3(mod 7),所以10²≡3²≡2(mod 7),10³≡3³≡2×3≡6≡-1(mod 7),因而10的6次方与1关于模7同余。于是10的6q次方除以7的余数均为1(q为正整数)。

为了把a的指数10的10次方写成6q+r的形式(r为正整数),还需取6为模来计算10的10次方.为此,我们有10≡4(mod 6),进而有10²≡4²≡4(mod 6),10³≡4³≡4(mod 6).以此类推,有10的10次方≡4(mod 6),所以10的10次方=6q+4。从而a≡10的(6q+4)次方≡10的6次方的q次方×10的4次方≡1的q次方×10的四次方≡3的四次方≡4(mod 7).

这样,星期一后的第a天(也就相当于是第四天)将是星期五。

我们有没有注意到在这个解题过程中,10的1次方一直到10的10次方它们都是与4关于模6同余的呢?也就是说它们除以6所得的余数都是4。那么10的n次方÷6的余数是否恒为4呢?答案是肯定的!证明方法如下:

方法一:

∵10≡4(mod 6)

∴10的n次方与4的n次方关于模6同余(n为正整数)

∴需证4的n次方除以6的余数恒为4

又∵4的n次方恒为2的倍数,且4≡1(mod 3)

∴4的n次方≡1的n次方(mod 3)

即4的n次方≡1(mod 3)

∴4的n次方除以3的余数恒为1

又∵4的n次方恒为2的倍数

∴可设4的n次方=x

∴x=3k+1(k为正整数),且x为偶数

∴3k+1为偶数

又∵1÷2余1

∴3k÷2余1

∴3k为奇数

∴k为奇数

设k=2m+1(m∈N)

∴4的n次方=x=3k+1=3(2m+1)+1=6m+4

∴4的n次方÷6=m余4

∴4的n次方除以6的余数恒为4

∴4的n次方≡4(mod 6)

又∵10的n次方≡4的n次方(mod 6)

∴10的n次方≡4(mod 6)

∴10的n次方÷6的余数恒为4

方法二:

∵10≡4(mod 6)

∴10的n次方与4的n次方关于模6同余(n为正整数)

∴需证4的n次方除以6的余数恒为4

∴需证4的n次方-4恒为6的倍数

∵4的n次方-4=2²的n次方-2²=2的n次方的平方-2²=(2的n次方+2)(2的n次方-2)

∴要将(2的n次方+2)(2的n次方-2)中的n分类讨论

当n=2k时(k为正整数),原式=(2的2k次方+2)(2的2k次方-2)=(4的k次方+2)(4的k次方-2)

∵4≡1(mod 3)

∴4的k次方≡1的k次方(mod 3)

∴4的k次方≡1(mod 3)

∴4的k次方÷3的余数恒为1

∴在式子(4的k次方+2)(4的k次方-2)中,4的k次方÷3的余数恒为1,所以(4的k次方+2)恒为3的倍数。

又∵(4的k次方-2)恒为2的倍数

∴(4的k次方+2)(4的k次方-2)恒为6的倍数

∴即当n为偶数时,4的n次方-4恒为6的倍数

当n=2k+1时(k∈N),原式=(2的2k+1次方+2)(2的2k+1次方-2)

=2×(2的2k次方+1)×2×(2的2k次方-1)

=2×(4的k次方+1)×2×(4的k次方-1)

又∵4的k次方÷3的余数恒为1

∴(4的k次方-1)恒为3的倍数

∴2×(4的k次方+1)×2×(4的k次方-1)恒为6的倍数

∴(2的2k+1次方+2)(2的2k+1次方-2)恒为6的倍数

∴即当n为奇数时,4的n次方-4恒为6的倍数

∴综上所述,当n为正整数时,4的n次方-4恒为6的倍数

∴即4的n次方除以6的余数恒为4

∴10的n次方÷6的余数恒为4

我们可以发现,方法一和方法二的前面的步骤都是利用同余的性质来解题的,只不过方法一是利用6可以写成2×3两个素数相乘的形式来入手解题的,方法二则是利用因式分解之后分类讨论来解题的。由此可见利用同余的性质解题是在解答数论类型题目中很普遍很重要的一种手段。

相关文章: