数学中国

用户名  找回密码
 注册
帖子
热搜: 活动 交友 discuz
查看: 4446|回复: 5

介绍一种简单的因子判别法

[复制链接]
发表于 2022-3-22 17:45 | 显示全部楼层 |阅读模式
介绍一种简单的因子判别法

作者 | 邵品琮 张景中 于劭

来源 |《数学通报》,1956(05)

当我们想知道一个整数能不能除尽另一个整数时,一般地,除了是用 2,3,5,…… 这些极个别的数去除别的数之外,总得老老实实去除一除。这件工作是很麻烦的。这里介绍一种方法,利用它能判别一个数能不能除尽另一个数,在我们只需要知道一个数能不能除尽另一数而不用知道它们的商时,这个方法是很适用的。

为了说着方便,当然可以假定除数 D 和被除数 N 都是正的。我们知道,被除数 N 越小,除起来就越省力;要是我们对于 D 和 N 能找到一个比 N 小的 R ,使得 D|R 是 D|N 的充分必要条件,那问题不是就简单了吗?这里介绍的方法的基本意思,就是给出一个规律,使我们对任意的正整数 D ,N ,都能找到一个比 N 小的 R ,满足:

D|R <=> D|N ( D|R 就是 D 能除尽 R 的意思)。

这个规律要是把它叙述成定理的形式,就是这样的:

“D ,N 都是正整数;N = 10a+b( 10>b ,a,b 都是正整数)则我们一定能找到一个只和 D 有关的整数 T ,使 D|R = a+Tb <=> D|N ”

(以后把 T 叫做 D 的“判别数”)。

这里先看一个例子;证明放在后面。

[例 1] 29 能不能除尽 899 ?

对 29 取判别数 T=3 。

899 = 10×89+9 ,故 a=89 ,b=9 。

故:R = a+Tb = 89+27 = 116 。

29 能除尽 116 吗?我们可以再化简一次:

116 = 10×11+6 ,故 a=11,b=6 ,

因而 R = a+Tb = 11+18 = 29 。

29 是能除尽 29 的;从而就能除尽 116 ,也就能除尽 899 。验算一下,就知道上述结论是对的。

我们要说明一下:对 D=29 取判别数 T=3 是对任意被除数 N 都成立的,这也放在后面证明。

下面证明,对任一除数 D ,总可以找到判别数 T ,而且具体地把它找出来:

(1)在 D 可以表成 10n+1 的情形下(n 正整数),我们取 T = -n ,则对任意被除数 N = 10a+b ,有 D|R = a+Tb <=> D|N 。

证明:

R = a-nb = a-n(N-10a) = a+10na-nN = a(10n+1)-nN = aD-nN 。

因为 D = 10n+1 ,所以 D 和 n 互素;上面的等式指出:D 能除尽 R 时 D 就能除尽 nN ,因而就能除尽 N 。反之,若 D 能除尽 N ,等式就直接指出:D 能除尽 R。

(2)当 D 可表为 10n+3 时(n 正整数),取 T = 3n+1 ,则对任意的被除数 N = 10a+b ,有 D|R = a+Tb <=> D|N 。

证明:

R = a+(3n+1)b = a+(3n+1)(N-10a) = N(3n+1)-30na-9a = N(3n+1)-3a(10n+3) = N(3n+1)-3aD 。

上面的等式指出:若 D 能除尽 R ,则 D 能除尽 N(3n+1) 。但是因为 D = 10n+3 = 3(3n+1)+n ,而 n 和 3n+1 互素,故 D 和 3n+1 也互素,所以,D 就能除尽 N 了。若 D 能除尽 N ,则等式直接说明,D 是能除尽 R 的。

一般说来,我们很容易证明下表所列之规律:

设被除数 N = 10a+b ,有:



从上表可以看出,例 1 中对 D=9 取 T=3 是正确的。

[例2] 41 是否能除尽 3731 ?

41 = 4×10+1 ,n=4 。41 是 10n+1 形式。

因而取 T = -n = -4 ,

R = 373+1×(-4) = 369 。

对 369 再用上述运算:

R = 36+(-4)×9 = 0 ,

所以,41 能除尽 3731 。

下面我们采用一种比较简单的写法,如:



故:41 | 3731 。

当 D 中有形式为 2^k×5^s 的因子,而 D/(2^k×5^s) 不再包含 2 及 5 的因子时( k,s 是自然数),我们可以把 D 是否能除尽 N 的问题化为 2^k×5^s 能否除尽 N 及  D/(2^k×5^s) 能否除尽 N 的问题了,而其中对 2^k×5^s 形式的因子判别法是众所周知的。

[例3] 问 95 能否除尽 3735 ?

95=19×5 ,显然 5|3735 。我们考虑 19 能否除尽 3735 :



因 19 除不尽 44 ,所以 19 除不尽 3735 ,结果得出结论:

95 不能除尽 3735 。

(本文系根据 Edwin Brenman, Testing for Divisibility, Scripta Mathernatica 1955 Vol. XXI,No.1,p.88-90 改写)

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
 楼主| 发表于 2022-3-25 18:59 | 显示全部楼层
下面是我过去在《数学中国》发表过的几个帖子,可供参考:




本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-3-25 19:00 | 显示全部楼层


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-3-25 19:01 | 显示全部楼层


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-3-25 19:02 | 显示全部楼层


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-3-25 19:04 | 显示全部楼层


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

LaTEX预览输入 教程 符号库 加行内标签 加行间标签 
对应的 LaTEX 效果:

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-8 22:54 , Processed in 0.107947 second(s), 17 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表
\frac{\square}{\square}\sqrt{\square}\square_{\baguet}^{\baguet}\overarc{\square}\ \dot{\baguet}\left(\square\right)\binom{\square}{\square}\begin{cases}\square\\\square\end{cases}\ \begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\to\Rightarrow\mapsto\alpha\ \theta\ \pi\times\div\pm\because\angle\ \infty
\frac{\square}{\square}\sqrt{\square}\sqrt[\baguet]{\square}\square_{\baguet}\square^{\baguet}\square_{\baguet}^{\baguet}\sum_{\baguet}^{\baguet}\prod_{\baguet}^{\baguet}\coprod_{\baguet}^{\baguet}\int_{\baguet}^{\baguet}\lim_{\baguet}\lim_{\baguet}^{\baguet}\bigcup_{\baguet}^{\baguet}\bigcap_{\baguet}^{\baguet}\bigwedge_{\baguet}^{\baguet}\bigvee_{\baguet}^{\baguet}
\underline{\square}\overline{\square}\overrightarrow{\square}\overleftarrow{\square}\overleftrightarrow{\square}\underrightarrow{\square}\underleftarrow{\square}\underleftrightarrow{\square}\dot{\baguet}\hat{\baguet}\vec{\baguet}\tilde{\baguet}
\left(\square\right)\left[\square\right]\left\{\square\right\}\left|\square\right|\left\langle\square\right\rangle\left\lVert\square\right\rVert\left\lfloor\square\right\rfloor\left\lceil\square\right\rceil\binom{\square}{\square}\boxed{\square}
\begin{cases}\square\\\square\end{cases}\begin{matrix}\square&\square\\\square&\square\end{matrix}\begin{pmatrix}\square&\square\\\square&\square\end{pmatrix}\begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\begin{Bmatrix}\square&\square\\\square&\square\end{Bmatrix}\begin{vmatrix}\square&\square\\\square&\square\end{vmatrix}\begin{Vmatrix}\square&\square\\\square&\square\end{Vmatrix}\begin{array}{l|l}\square&\square\\\hline\square&\square\end{array}
\to\gets\leftrightarrow\nearrow\searrow\downarrow\uparrow\updownarrow\swarrow\nwarrow\Leftarrow\Rightarrow\Leftrightarrow\rightharpoonup\rightharpoondown\impliedby\implies\Longleftrightarrow\leftharpoonup\leftharpoondown\longleftarrow\longrightarrow\longleftrightarrow\Uparrow\Downarrow\Updownarrow\hookleftarrow\hookrightarrow\mapsto
\alpha\beta\gamma\Gamma\delta\Delta\epsilon\varepsilon\zeta\eta\theta\Theta\iota\kappa\varkappa\lambda\Lambda\mu\nu\xi\Xi\pi\Pi\varpi\rho\varrho\sigma\Sigma\tau\upsilon\Upsilon\phi\Phi\varphi\chi\psi\Psi\omega\Omega\digamma\vartheta\varsigma\mathbb{C}\mathbb{H}\mathbb{N}\mathbb{P}\mathbb{Q}\mathbb{R}\mathbb{Z}\Re\Im\aleph\partial\nabla
\times\cdot\ast\div\pm\mp\circ\backslash\oplus\ominus\otimes\odot\bullet\varnothing\neq\equiv\not\equiv\sim\approx\simeq\cong\geq\leq\ll\gg\succ\prec\in\ni\cup\cap\subset\supset\not\subset\not\supset\notin\not\ni\subseteq\supseteq\nsubseteq\nsupseteq\sqsubset\sqsupset\sqsubseteq\sqsupseteq\sqcap\sqcup\wedge\vee\neg\forall\exists\nexists\uplus\bigsqcup\bigodot\bigotimes\bigoplus\biguplus\bigcap\bigcup\bigvee\bigwedge
\because\therefore\angle\parallel\perp\top\nparallel\measuredangle\sphericalangle\diamond\diamondsuit\doteq\propto\infty\bowtie\square\smile\frown\bigtriangledown\triangle\triangleleft\triangleright\bigcirc \wr\amalg\models\preceq\mid\nmid\vdash\dashv\nless\ngtr\ldots\cdots\vdots\ddots\surd\ell\flat\sharp\natural\wp\clubsuit\heartsuit\spadesuit\oint\lfloor\rfloor\lceil\rceil\lbrace\rbrace\lbrack\rbrack\vert\hbar\aleph\dagger\ddagger

MathQuill输入:

Latex代码输入: