Признаки делимости целых и рациональных чисел

Получены новые признаки делимости целых и рациональных чисел на любой целый или рациональный делитель, не равный нулю.

Из общего алгоритма получены новые признаки делимости целых и рациональных чисел на любой целый или рациональный делитель, не равный нулю. Рассмотрим сначала признаки делимости целых чисел. Целое число запишем в виде a = bc , где b — произвольное целое число, не равное нулю; c — m -значное целое число, m е N , N – множество натуральных чисел. Число b в числе (a) смещено влево на m десятичных разрядов, т.е.

a = b • 10^m + c , (1)

где

b =

a

10m

целая часть от деления, c = a — b • 10^m

Целочисленный n-значный делитель p

где k – некоторый целочисленный коэффициент редукции. Признаки делимости целого числа на целочисленный делитель определяются следующей теоремой.

Теорема 1. Целое число делится без остатка на целочисленный делитель, если на этот делитель делится без остатка редукция данного числа. Доказательство. Пусть число (a) и его редукция r делятся без остатка на делитель p, тогда запишем a b • 10m + c . r k • b + c

• - =            = i , -=         = j ,          (3)

pp  pp где i, j е N . Вычитая в (3) одно равенство из другого, получим

1 — j = b (10^m— k) .                                  (4)

p

Правая часть равенства (4) будет целочисленной, если 10m — k = lp и l – целое, откуда находим коэффициент редукции k = 10m - Ip , l = 0, ± I, ± 2,...                     (5)

Из равенств (3) ^ (5) вытекает доказательство теоремы.

Для одного и того же делителя p и постоянного значения m можно по формуле (2) образовать цепочку редукций, в которой для каждой новой редукции за число bc принимается предыдущая редукция. Для отрицательных значений k редукция r может оказаться отрицательной и если она используется для образования новой редукции, то знак “–” относится к обеим числам b и c. Из формул (1) и (2) следует: цепочка редукций является конечной для |k| < 10m и бесконечной для |k| > 10m , при |k| = 10m число bc переходит само в себя. Количество разрядов m числа (c) можно выбрать любым при условии , что c

Пусть задано начальное число b₀c₀= b₀• 10m + c₀ , тогда для делителя p и коэффициента редукции k существует цепочка редукций:

Г, = ^k• ^bv-1 ⁺cv-1 , rv = bvcv = bv • ¹⁰m ⁺cv , ^V = ^1,2,"•    ⁽⁶⁾

rv 10^m

bv

• ; для rv < 0 и bv < 0: cv = r - bv • 10m, v = 1, 2,... (7)

Для конечной цепочки редукций процесс вычисления закончится, когда для вновь образованной редукции при некотором значении v будет выполнено неравенство |iv | < 10m , откуда с учетом (7) следует b_v+t= 0 , c_v+t= r_v, t = 1,2,... . В бесконечной цепочке редукций для некоторых k<0 возможно периодическое повторение нескольких редукций. Такие цепочки также будем считать конечными, т.к. процесс вычисления редукций зацикливается на нескольких повторяющихся редукциях.

Из равенства (5) следует независимость коэффициента редукции от чисел b и c, следовательно для одного и того же делителя p и некоторого фиксированного коэффициента редукции k = k0 , проверяется делимость произвольного целого числа в соответствии с приведенной выше теоремой 1. Если из (5) выбрать некоторый фиксированный коэффициент редукции k = k0 , то все множество коэффициентов редукции, определяемых в (5), можно выразить формулой k = k0 + lp , l = 0, ± 1, ± 2,... ,                    (8)

которая проще для использования. Число (c) в (1) имеет m десятичных разрядов, а делитель p имеет n разрядов; m и n могут быть разными, но для практики удобнее когда m = n . Наименьшие неотрицательные значения k из (5) при постоянных m и p будем называть начальными коэффициентами k0 редукции, которые для m p < 10 являются наименьшими неотрицательными вычетами чисел 10m по модулю p, определяемыми из равенства 10m = lp + k0 , где l

– частное, а k0 – остаток от деления 10m на p :

l =

10m

p

k_o= 10m -lp = |i0m|_p

0 < k0 < p ,

Если известно, что число (a) делится на p, то из формул (4) и (5) результат деления можно записать в виде i = b • l + j ,                                                    (10)

где j вычисляется по формуле (3). Для цепочки из s редукций, определяемых в (6) и (7), результат деления (a) на p запишется в виде i = l §bv+ jt , t = 1, 2,... ,s,                       (11)

v=0

где j_t =r_t /p , числа b_v(v > 1) определяются из (7), b₀=

a

10m

l

определяется из (5) при известном коэффициенте k редукции для любых p, если же p < 10m и k > 0, то l можно определить также и из (9). Формула (11) позволяет действие деления двух чисел заменить на несколько сложений целых чисел, одно умножение на целое число l и одно несложное деление последней редукции на делитель p.

Проиллюстрируем образование цепочки редукций на примере. Возьмем число а₀= 952 , которое делится на p=7, (952 : 7=136). Выберем m=1, из (9) вычислим коэффициент редукции k = 10¹= 3 . Взятое число a₀= b_nc_n= 952 , a₀= 95 • 10¹+ 2 , где ₇             000      0

b₀= 95 , c₀= 2 . Цепочку редукций строим по формулам (6) и (7) с учетом чисел b₀,c₀ :

952^3^95+2=287^3^28+7=91 ^3^9+1=28^3^2+8=14^3^1+4=7 .

Подчеркнутые части чисел являются числами b . Получили цепочку из s=5 редукций, каждая из которых делится на 7. Имеем: b₀= 95, b1 = 28, b₂= 9, b₃= 2, b₄= 1. Результат деления 952 : 7

можно вычислить по формуле (11), в которой t=1, 2,…, s ; выберем t=s=5, l=[10 / 7]=1, jt =rt /7=7/7=1, тогда получим:

952 : 7=1-(95+28+9+2+1)+1=136 .

Все выше изложенное можно применить и к рациональным числам, представленным в виде конечных десятичных дробей. Числа a, c, p, r, k, k₀, l могут быть как целыми, так и конечными десятичными дробями; i, j – любые рациональные числа; числа b – только целые; m,n е N; m определяет количество десятичных разрядов в целой части числа c. Результатом деления (a) на p может быть как целое число, так и конечная или бесконечная десятичная дробь. Для целочисленных (a) и p, когда результат их деления – целое число, признаки делимости определяются теоремой 1, обобщением которой является следующая теорема.

Теорема 2. Пусть каждое из чисел a и p является либо целым, либо конечной десятичной дробью. Результатом деления числа a на p является целое число, конечная или бесконечная десятичная дробь, если результатом деления редукции r числа a на p также является соответственно целое число, конечная или бесконечная десятичная дробь.

Доказательство теоремы такое же, что и для теоремы 1, только некоторые числа в (3)^(5) могут быть как целыми, так и десятичными дробями. Определенное при доказательстве теоремы равенство (5) в этом случае позволяет выбрать одно из чисел k, l либо целым, либо в виде конечной десятичной дроби, при этом по-прежнему l может быть как положительным, так и отрицательным. Для случая p < 10^m равенства (9) также можно использовать, считая l целым положительным всегда, а остаток k₀= 10^m— lp может быть как целым, так и конечной десятичной дробью.