«Признаки делимости в различных системах счисления»



Скачать 244.12 Kb.
Дата19.01.2013
Размер244.12 Kb.
ТипРеферат


Министерство образования и науки Республики Казахстан
Секция математики

«Признаки делимости в различных системах счисления»

Выполнила:

ученица Технического лицея

11 «Б» класса Кзылова Айдана

Научный руководитель: Емелина Наталья Константиновна

кандидат экономических наук

Караганда 2008

Аннотация

Данная работа посвящена исследованию признаков делимости в различных системах счислениях. Здесь рассматриваются признаки делимости для натуральных чисел в десятеричной системе счисления, малая теорема Ферма, элементы комбинаторики, понятие факториала.
Аңдатпа

Тап осы жұмыс бөліну белгілерінің зерттеуіне арналған әртүрлілерді жүйелерде санауларда. Бул жерде рассматриваются натурал сандардыларға арналған бөліну белгілері санау – жүйесіне қаралады, шағын теорема Ферма, комбинаторика элементтері, факториал ұғымы.

Содержание

Введение 3

§ 1. Системы счисления 10

§ 2. Признаки делимости в десятеричной системе 14

§ 3. Признаки делимости в различных системах счисления 15

§ 4. Область применения n! 22

§ 5. Малая теорема Ферма 24

Заключение 25

Список использованной литературы 26

Дневник исследователя 27

Введение

Цели:

1) исследование признаков делимости для натуральных чисел в десятеричной системе счисления;

2) выведение более простого пути доказательства этих признаков;

3) доказательство малой теоремы Ферма;

4) рассмотрение различных систем счисления, понятия факториала, элементов комбинаторики;

Гипотеза
В основу данной работы была положена гипотеза о том, что признаки делимости зависят от системы счисления и свойств чисел. Другим составным элементом гипотезы являлось теоретическое положение о существовании универсального признака делимости для любой системы счисления.

Этапы исследования:

1) доказаны признаки делимости для 4,6,9,11.

2) выведен универсальный признак делимости

3) найдено частное от деления для р-2, р-3, р-4, р-5.

Методика эксперимента:

Для доказательства теорем и признаков делимости был использован метод математической индукции.


Новизна исследования и степень самостоятельности

Самостоятельно исследователем было выполнено следующее:

  1. доказательство признаков делимости

  2. установлены закономерности в различных системах счисления

  3. доказан универсальный признак делимости


Результаты работы и выводы

  1. выведены закономерности в различных системах счисления

  2. представлен наиболее простой путь доказательства признаков делимости


Области практического использования результатов

  1. для вычисления биноминальных коэффициентов

  2. при доказательстве теоремы о максимальной степени простого числа делящего

  3. теорема о произведении всех простых чисел


§ 1. Системы счисления

Основанием позиционной системы счисления может быть любое натуральное число Для записи чисел в системе счисления с основанием q необходимо q символов. Например, в Древнем Вавилоне была создана система счисления (точнее система мер), в основании которой лежало число 60. Полностью эта система выдерживалась у вавилонян для измерения времени и углов. Деление часа и градуса на 60 минут, минуты – на 60 секунд мы унаследовали именно от них. В измерении весов наблюдалось некоторое отступление от этого правила: один талант содержал 60 мин, одна мина – 60 сиклей, а один сикль – 180 зерен, что составляло приблизительно 10 граммов по современному счету.

Число 60 кратно 2, 3, 4, 5, 6, 12, 15, 20, 30, 60. Такое обилие делителей у сравнительно небольшого числа упрощало расчеты: из шестидесяти предметов половиной являются тридцать из них, третью – двадцать, четвертой частью – пятнадцать и т.д.

Из этих соображений, как полагает Теон Александрийский (конец IV и начало V в н.э.), и возникла у вавилонян шестидесятеричная система нумерации. Такой же точки зрения придерживался и выдающийся математик XVII века Валлис, позднее к ним присоединился Лефлер.

Возможно, что разделение вавилонянами года на 360 дней (излишек компенсировался добавлением месяца в некоторые годы) дало им повод разделить окружность на 360 частей (шагов) считая, что солнце при видимом его обращении вокруг Земли делает за сутки на один шаг. Такое деление окружности на 360 равных частей (градусов) сохранилось и до нашего времени. Градус в переводе с латинского, как раз и означает шаг.

Вавилонянам был известен простой способ деления окружности на шесть равных частей (колеса у их колесниц, например, всегда делались с шестью спицами). Этот удобный способ деления круга на шесть «секстантов» лег в основу гипотезы Кантора, так как дуга секстанта делилась на 60 градусов (это же объяснение приводил еще в 1781 году итальянец Формлоени, исходя из курьезной точки зрения, что в «эпоху потопа» год был короче нынешнего и составлял ровно 360 дней) .

Астрономические и геометрические соображения, лежащие в основе обоснования шестидесятеричной системы вавилонского счета, в настоящее время серьезно и обоснованно оспариваются из-за слабой мотивировки. См Кантор впоследствии отказался от своей гипотезы и принял гипотезы Г.Кевича, согласно которой, шестидесятеричная система возникла как симбиоз двух систем – десятеричной и шестеричной, существовавших прежде, независимо друг от друга, у суммерийцев и аккадян.

О. Нойгебауэр считает, что торговые сношения между этими народами потребовали установления некоторого эквивалента между их весовыми единицами – миной и шекелем. Шестая часть мины была приравнена к десяти шекелям. Отсюда возник эквивалент мины и шекеля: 1 мина = 60 шекелей.

Двенадцатеричная система счисления использовалась древними египтянами, хозяйственная деятельность которых существенным образом зависела от годовых колебаний уровня воды в Ниле. Этапы сельскохозяйственных работ египтян определили разбивку год на 12 месяцев по 30 суток в каждом (недостающие пять дней добавлялись в конце года как праздничные). Каждые сутки разделялись на двадцать четыре часа: двенадцать ночных и двенадцать дневных. Дневные и ночные часы различались между собой по продолжительности, так как дневной час представлял собой 1/12 часть дня от восхода солнца и до его захода, а ночной – 1/12 часть ночи от захода Солнца до его восхода.

Некоторые народности имели для обозначения чисел 1 или 2, 3, 4, а все остальные количества называли словом «много» (так называемое двойственное число). В русском языке, например, сохранились остатки счета до четырех. Мы говорим 2, 3, 4 руки, но 5, 6 и вообще много рук. Самым трудным этапом при выработке человеком понятия числа считается выделение единицы из понятия «много». В.В.Боборыкин (1849-1919) объясняет это тем, что человек обычно захватывает рукой один предмет, выделяя его из множества подобных. Племя ботокудов (Бразилия) выражало числа только словами «один» и «много».

Две руки человека привели к счету до двух. Четыре конечности человека и животных, в южных землях четыре пальца страуса – к счету до четырех. Десять пальцев – к повсеместно распространенной десятичной системе. Двадцать всех пальцев рук и ног человека привели к двадцатеричной системе счислении, которой пользовались южноамериканское племя майя. У североамериканских эскимосов «человек» служит выражением числа 20. Двадцатеричная система имеет существенный недостаток – для ее словесного выражения нужно иметь двадцать различных названий чисел первого разряда. Поэтому от нее постепенно отошли, переняв десятичную. Этому, возможно, способствовало употребление обуви. Двадцатеричная система в чистом виде не употребляется ни у одного народа, лишь только соединяясь с десятичной или пятеричной. Однако следы ее сохранились. У французов, например, число 80 выражается словом quatre-vingts (четырежды двадцать), 90 – словом quatre-vingt-dire (четырежды двадцать и десять). В русском языке число 40 (сорок) выпадает из общего принципа словообразования десятков; это остаток счета сороковками (обычный объем бочки – 40 литров, на современных пушных аукционах выставляют связки по сорок шкурок ценной пушнины).

Системой счисления называют способ записи чисел с помощью заданного набора специальных знаков или цифр. В двоичной системе счисления всего два таких знака, это 0 и 1. Двоичная система счисления используется в вычислительных машинах. Выбор двоичной системы объясняется тем, что электронные элементы, из которых строились и строятся ЭВМ, могут находиться только в двух хорошо различимых устойчивых рабочих состояниях. Словом, эти элементы представляются нам в роли выключателей. А как мы все знаем, выключатель может быть включен или выключен. Третьего не дано. Одно из состояний выключателя обозначается 0, а другое — 1. Теперь покажем, как переводить числа из десятеричной системы счисления в двоичную.


Позиция

10

9

8

7

6

5

4

3

2

1

0

Значение

1024

512

256

128

64

32

16

8

4

2

1

Весовой эквивалент

























Пример 1: перевести

Позиция

3

2

1

0

Число

1

1

0

1

Весовой эквивалент

8

4

2

1





Пример 2: перевести


Далее рассмотрим запись числа в десятеричной системе счисления:
Запишем число 458 в десятеричной системе:



458=8+510+4100

-последняя цифра

-первая цифра


Теперь рассмотрим запись числа в двоичной системе счисления:

нули и единицы



Например:

25=1+02+04+18+116

сумма цифр в двоичной системе
Запись числа в p-ичной системе счисления:

, где

Сумма цифр в р-ичной системе:



§ 2. Признаки делимости в десятеричной системе
На основе изученных систем счислений можно доказать признаки делимости для этих систем счислении.

Докажем признак делимости на 9:

Если от числа отнять сумму его цифр, то результата всегда будет делиться на 9.

Вывод: таким образом, мы доказали, что если от числа отнять сумму его цифр, то результат всегда будет делиться на 9. Следовательно, число n делится на 9, тогда и только тогда, когда сумма его цифр делится на 9.

Докажем признак делимости на 11:

Если от числа отнять знакочередующийся ряд его цифр, то результат всегда будет делиться на 11.





-последняя цифра

-первая цифра





Доказательство:

Вывод: таким образом, мы доказали, что если от числа отнять знакочередующийся ряд его цифр, то результат будет делиться на 11.

§ 3. Признаки делимости в различных системах счисления

Теперь докажем универсальный признак делимости в десятичной системе счисления:

Т.к. -это остатки от делении чисел на m, то разность , , делится на m

ч.т.д.

Следовательно, универсальный признак делимости гласит:

Число n делится m, тогда и только тогда, когда сумма произведений его цифр на соответствующие остатки от деления чисел на m, делится на m; т.е. делится на m. Рассмотрим этот признак для m=7,9,6
Проверим этот признак для m=7.

Получаем последовательность :

10:7=1(3) 10000:7=1428(4)

100:7=14(2) 100000:7=14285(5)

1000:7=142(6) 1000000:7=142857(1) и т.д.

Т.е. : 3;2;6;4;5;1…

Остаток при делении числа, например, 1992=2+93+92+16=53=3+53=18=8+13=11=1+13=4.

Следовательно, число 1992-4=1988 делится на 7.

Проверим:

1988 7

14 284

58

56

28

28

0 ч.т.д.
Проверим признак делимости для m=9.

Пусть m-натуральное число и - остатки чисел при делении на m. Тогда число n- делится на m.

Проверим этот признак для m=9.

10:9=1(1) 10000:9=1111(1)

100:9=11(1) 100000:9=11111(1)

1000:9=111(1) 1000000:9=1111111(1) и т.д.

Т.е. : 1;1;1;1;1;1…

Остаток при делении числа, например 1992=2+91+91+11=21=1+21=3.

Следовательно, число 1992-3=1989 делится на 9.

Проверим:

1989 9

18 221

18

18

9

9

0 ч.т.д.
Проверим признак делимости для m=6.

Пусть m-натуральное число и -остатки чисел при делении на m. Тогда число n- делится на m.

Проверим этот признак для m=6.

10:6=1(4) 10000:6=1666(4)

100:6=16(4) 100000:6=16666(4)

1000:6=166(4) 1000000:6=166666(4) и т.д.

Т.е. : 4;4;4;4;4;4…

Остаток при делении числа, например

5672=2+74+64+54=7+4=11=2.

Следовательно, число 5672-2=5670:6=945 ч.т.д.


Далее целью нашей работы является определить делится ли на (р-1) и чему равно частное.

- частное от деления

- сумма цифр в р-ичной системе счисления

Теорема 1. делится на (p-1)
Доказательство:



ч.т.д.
Например, в восьмеричной системе счисления число, записанное как , делится на 7.

4+28+164=

Т.е. если сумма цифр числа записанного в восьмеричной системе счисления делится на 7, то это число делится на 7 в десятичной системе счисления.

Докажем, что



Т.е. если сумма цифр числа записанного в шестеричной системе счисления делится на 5, то это число делится на 5 в десятичной системе счисления.

Необходимо выяснить чему равно частное от деления:


Начнем с р = 2









0

0

0

0

1

1

1

0

2

10

1

1

3

11

2

1

4

100

1

3

5

101

2

3

6

110

2

4

7

111

3

4

8

1000

1

7

9

1001

2

7

10

1010

2

8

11

1011

3

8

12

1100

2

10

13

1101

3

10

14

1110

3

11

15

1111

4

11

Закономерность:

  1. при каждом нечетном n число δ(n) не меняется.

  2. При каждом четном n число δ(n) меняется на столько, сколько нулей в конце двоичной записи числа n. А число нулей есть максимальная степень двойки, на которую делится n.



δ(n) считает, сколько степеней двойки есть в числах 1,2,… n или в их произведении (n!).

Вывод: есть максимальная степень двойки, на которую делится число n!

Теорема 2.

есть максимальная степень двойки, на которую делится число n!

Доказательство:

Используем метод математической индукции. Осуществим индукционный переход. Допустим, что для (n-1) мы уже получим нужный результат:

есть максимальная степень 2, на которую делится (n -1)!

Докажем для n.

Число n! Отлично от (n-1)! тем, что оно больше в n раз. Значит, появится ровно столько новых степеней двойки, сколько их есть в числе n, а это как раз число нулей в конце двоичной записи числа n.

по сравнению с : n по сравнению с (n-1) увеличили на 1. А как изменится по сравнению с ?

Допустим, что в конце двоичной записи числа n стоит К нулей:

Тогда (n-1) имеет вид: , значит, число единиц стало на (К-1) меньше. Следовательно, 1-(-(К-1))=1+К-1=К.

Тем самым индукционный переход оказывается верным.
В общем случае:



есть максимальная степень р, делящая n!
Проверим для р=3

, где р=3











0

0

0

0

1

1

1

0

2

2

2

0

3

10

1

1

4

11

2

1

5

12

3

1

6

20

2

2

7

21

3

2

8

22

4

2

9

110

2

7/2

10

101

2

4


Проверим для р=5

, где р=5









0

0

0

0

1

1

1

0

2

2

2

0

3

3

3

0

4

4

4

0

5

10

1

1

6

11

2

1

7

12

3

1

8

13

4

1

9

14

5

1

10

20

2

2

Проверим для р=4
, где р=4











0

0

0

0

1

1

1

0

2

2

2

0

3

3

3

0

4

10

1

1

5

11

2

1

6

12

3

1

7

13

4

1

8

20

2

2

9

21

3

2

10

22

4

2


Но при р=4 нас ждет разочарование. Число 6! делится на , но . Причина заключается в том, что эта формула действует при простых р.

§ 4. Область применения n!

Для решения вопросов о делимости кроме простых чисел нам больше ничего не нужно. Но что нам делать с факториалом, куда приспособить только что полученные знания? Безусловно, в первую очередь для биноминальных коэффициентов (которые иногда обозначают и по-другому: ).

Главная формула, с которой они связаны,- это бином Ньютона:



Для больше симметрии используем такое обозначение:



В результате полученных значений, мы способны определить, на какую степень простого числа р делится данный биноминальный коэффициент. Она в точности равна:

Например, если ,

то на р не делится, и наоборот. Рассмотрим случаи, когда такое бывает. Например, при сложении в р-ичной системе счисления чисел m и n переносов из разряда в разряд не происходит. Скажем, если сложить числа, записанные в семеричной системе счисления как 23 и 32, то получим 55 без переносов.

Вывод: так как , то на 7 не делится.

А если перенос есть? Допустим, в каком-то разряде i. Скажем, у m было число r. Оказывается на (p-1) мы и делим. Тогда верна следующая теорема:
Теорема 3. Если р – простое число, то максимальная степень р, делящая , равна количеству переносов при сложении чисел m и n в р-ичной системе счисления.

Для доказательства данной теоремы начнем с изучения - самого большого биноминального коэффициента среди всех, входящих в разложение бинома Максимальная степень р, на которую он делится, равна количеству переносов, получающихся при сложении n с самим собой в р-ичной системе счисления. Допустим, что n
Тогда n р-ичной системе записывается одной р-ичной «цифрой» (собственно n), а 2n – двумя, скажем, Это значит, что происходит ровно один перенос и, следовательно, р входит в ровно один раз. Таким образом, произведение всех простых чисел, заключенных между n и 2n, не превосходит . Оценим грубо.

Если положить в биноме Ньютона x=y=1, то получится, что:

, откуда <.

Точно таким же образом произведение всех простых чисел между n/2 и n меньше , между n/4 и n/2 – меньше и т.д. Тогда произведение всех простых чисел между 1 и n меньше:



В итоге мы получили совсем неочевидный факт:

Теорема 4. Произведение всех простых чисел, меньших n, не превосходит .

§5. Малая теорема Ферма

Используя все выше доказанное мы докажем малую теорему Ферма:

Малая теорема Ферма — классическая теорема теории чисел, утверждает что: для любого простого и целого, делится на

Доказательство


Докажем, что для любого простого p и целого неотрицательного a, apa делится на p. Доказываем индукцией по a.

База. Для a=0, apa = 0 и делится на p.

Переход. Пускай утверждение верно для a=k. Докажем его для a=k+1.





Но kpk делится на p по предположению индукции. Что же касается остальных слагаемых, то . Для , числитель этой дроби делится на p, а знаменатель — не делится, следовательно, делится на p. Таким образом, вся сумма делится на p.Для отрицательных a и нечётных p теорему легко доказать подстановкой b=-a. Для отрицательных a и p=2, истинность теоремы следует из a2a = a(a − 1)

Заключение.

В данной исследовательской работе нами были сделаны следующие выводы:

1) если от числа отнять сумму его цифр, то результат всегда будет делиться на 9. Следовательно, число n делится на 9, тогда и только тогда, когда сумма его цифр делится на 9;

2) если от числа отнять знакочередующийся ряд его цифр, то результат будет делиться на 11;

3) число n делится m, тогда и только тогда, когда сумма произведений его цифр на соответствующие остатки от деления чисел на m, делится на m; т.е. делится на m;

4) есть максимальная степень двойки, на которую делится число n!;

5)

есть максимальная степень р, делящая n!;

6) данная формула действует только при простых р;

Список использованной литературы


  1. Журнал «Квант», №6,1992г.

  2. «Теория чисел», Абляева Ф., Иванова Н., Букетова

  3. «Теория чисел», А.А. Бухштаб

  4. «Основы теории чисел», А.Вейль

  5. «Основы теории чисел», И.Виноградов

  6. Журнал «Квант», №8,1976г.




Похожие:

«Признаки делимости в различных системах счисления» iconУроках в 10 классе (базовый уровень) по аналогичной теме). Тема урока
Тема урока: Представление числовой информации в различных системах счисления. Перевод чисел из одной системы счисления в другую и...
«Признаки делимости в различных системах счисления» iconУрок №19-20. Тема Арифметические операции в позиционных системах счисления. Умножение и деление
Цель урока: показать способы арифметических операций (умножения и деления) чисел в разных системах счисления, проверить усвоение...
«Признаки делимости в различных системах счисления» icon«Перевод чисел в позиционных системах счисления»
Цель: Проверка усвоения теоретических знаний по способам представления чисел в позиционных системах счисления, формирование умений...
«Признаки делимости в различных системах счисления» iconСистемы счисления
Цель урока: закрепление, обобщение и систематизация знаний учащихся по теме «Системы счисления» правил перевода и выполнения арифметических...
«Признаки делимости в различных системах счисления» iconПлан-конспект урока Системы счисления(10 класс)
Цель урока: закрепление, обобщение и систематизация знаний учащихся по теме «Системы счисления» правил перевода и выполнения арифметических...
«Признаки делимости в различных системах счисления» iconУрок №4 1 Тема Арифметические операции в позиционных системах счисления. Сложение и вычитание
Цель урока: показать способы арифметических операций (сложения и вычитания) чисел в разных системах счисления
«Признаки делимости в различных системах счисления» icon«Признаки делимости на 10, на 5 и на 2»
Используя признак делимости на 5 число, определи, делится ли на 5 число, составленное только из двоек
«Признаки делимости в различных системах счисления» iconПрограмма вступительных испытаний «математика» Теория чисел, алгебраические преобразования : д есятичная система счисления, п ростые и составные числа, признаки делимости чисел, д еление с остатком, д
Виета, числовые неравенства и их свойства, метод интервалов, рациональные выражения, модуль, уравнения высших степеней
«Признаки делимости в различных системах счисления» iconПозиционные и непозиционные системы счисления. Построение натурального ряда в позиционных системах счисления
Система счисления (СС) – это способ записи чисел и соответствующие ему правила действий над ними
«Признаки делимости в различных системах счисления» iconПлан-конспект №4 по математике в 6 классе Учитель: Ференчук Людмила Вячеславовна Тема урока: Признаки делимости на 10, на 5 и на 2 Цели урока Изучение признаков делимости чисел на 10, 5 и на 2
Развитие аргументированной речи, доказательного воспроизведения в процессе деятельности
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org