Теория чисел

Размещено на http://www.allbest.ru/

1. Отношение делимости в кольце целых чисел. Свойства

Говорят, что целое число a делится на целое число b, отличное от 0, если такое целое число с, определенное однозначно, что a=b*c.

Свойства: евклид лемма арифметика позиционный

1) Отношение делимости рефлексивно, т.е. . Действительно, число 1, а=а*1

2) Отношение делимости транзитивно, т.е. если

Из этого следует, что a=(c*k)*t=c*(k*t)=c*m

А это значит, что ас

3) Если аb, то (-a)b, (-a)(-b), a(-b)

4) Если ac и bc, то (ab)c

a=c*t, b=c*k (ab)=c*tc*k=c*(tk)(ab)c

НО: обратное утверждение неверно.

5) Если ab и cZ (произвольное число), то (a*c)b

6) Если каждое из чисел a1, a2…an делится на b, то (r1a1+…+rnan)b, где r1,…,rnZ

7) Если ac, b неc, то (a+b)нес

Пусть (a+b)=t и tc, t-a=b это противоречит условию.

8) 0на любое число, 0

9) Всякое целое число1, т.к. всякое число можно записать в виде а=1*а

10) На 0 делить нельзя: а=0*с, если а0, то это равенство неверно; если а=0, то имеем 0=0*с, сZ - в этом случае нарушается условие единственности определения с.

11) Если ab,то . a=b*c, , где b,cZ

2. Теорема о делении с остатком

Разделить целое число а на целое число b0, это значит найти такие целые числа q и r, что a=bq+r, 0

Теорема: в кольце целых чисел всегда возможно выполнение деления с остатком и причем единственным образом.

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

1) Существование:

Рассмотрим целые числа кратные b. Это числа -2b,-b,b,2b… и пусть bq-последнее кратное b, не превышающее число а, тогда оно является наибольшим среди записанных кратных. В этом случае b(q+1)>a. Получили:

bqa<b(q+1), bqa<bq+b (-bq) 0a-bq<b

Пусть a-bq=r. Тогда получим: a=bq+r, причем 0r<

Это доказательство проходит для случая b>0.

Теперь пусть b<0,тогда (-b)>0.

Тогда a=(-b)*q+r, a=b*(-q)+r, где 0r<-b, -b=, где b<0, 0r<

Таким образом, деление с остатком возможно при любых а и b0

2) Единственность:

Предположим, что это не так:

a=bq1+r1 и a=bq2+r2;

bq1+r1=bq2+r2;

b(q1-q2)=r2-r1; где 0r1,r2<;

=;

, где 0r2-r1<, r2>r1.



Равенство возможно, если , =>q1=q2, r1=r2.

Следовательно, деление с остатком однозначно: q-неполное частное, r-остаток.

3. Наибольший общий делитель

Общим делителем целых чисел a и b называется целое число t, на которое делится а и b (at и bt).

НОД целых чисел а и b называется их общий делитель, который делится на любой другой общий делитель этих чисел.

НОД целых чисел определен однозначно с точностью до знака.

Свойства НОД:

1) если НОД(а,b)=d, то НОД(ak,bk)=dk

2) если НОД(a,b)=d, то НОД(a/n, b/n)=d/n

3) если НОД(a,b)=d, то x,yZ, что ax+by=d - линейное представление НОД

4) если НОД(a1,a2…an-1)=d1 и НОД(d1,an)=d, то НОД(a1,a2…an)=d

Из 4го св-ва следует правило нахождения НОД для нескольких чисел:

НОД(a1,a2)=d1 НОД(d1,a3)=d2 НОД(d3,a4)=d d=НОД(a1,a2,a3,a4)

4. Алгоритм Евклида

Алгоритм Евклида - метод нахождения НОД(a,b), основанный на следующих 2х леммах:

1) Если ab, то НОД(a,b)=b

2) Если целое число а делится на b с остатком, то НОД(a,b)=НОД(b,r)

Алгоритм Евклида для целых чисел а и b представляет собой следующее последовательное деление:

а делится с остатком на b

a=bq0+r1

b=r1q1+r2

r1=r2q2+r3

………..

Rn-2=rn-1qn-1+rn

Rn-1=rnqn+0

Т.к. остатки последовательно уменьшаются, то процесс деления конечен.

Теорема: Последний отличный от 0 остаток в алгоритме Евклида чисел а и b яаляется их НОД.

5. Наибольший общий делитель

Общим делителем целых чисел a и b называется целое число t, на которое делится а и b (at и bt).

НОД целых чисел а и b называется их общий делитель, который делится на любой другой общий делитель этих чисел.

НОД целых чисел определен однозначно с точностью до знака.

Свойства НОД:

1) если НОД(а,b)=d, то НОД(ak,bk)=dk

2) если НОД(a,b)=d, то НОД(a/n, b/n)=d/n

3) если НОД(a,b)=d, то x,yZ, что ax+by=d - линейное представление НОД

4) если НОД(a1,a2…an-1)=d1 и НОД(d1,an)=d, то НОД(a1,a2…an)=d

Из 4го св-ва следует правило нахождения НОД для нескольких чисел:

НОД(a1,a2)=d1 НОД(d1,a3)=d2 НОД(d3,a4)=d d=НОД(a1,a2,a3,a4)



6. Взаимно простые числа

Взаимно простыми числами называются целые числа, НОД которых равен 1.

Т:Целые числа a и b взаимно просты тогда и только тогда, когда х,у такие, что ax+by=1

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

1. Пусть а и b взаимно простые, следовательно НОД(а,b)=1. По свойствам х,у, ax+by=1

2. Пусть числа х,у, для которых ax+by=1. Предположим ,что НОД (а,b)=d, тогда аd и bd=>1d=>d=1, d=1

Следовательно, НОД(а,b)=1, т.е. числа взаимно простые.

Следствие: Если а,b-взаимно просты, аа1 и bb1, то числа а1 и b1 также взаимно простые.

Т: Частные от деления целых чисел а и b на их НОД взаимно простые.

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

НОД(a,b)=d, тогда х,уZ, такие что ax+by=d; - взаимно простые.

7. Свойства взаимно простых чисел

1)

ax+cy=1 (*b)

(ab)x+(cb)y=b

2) Если (а,b)=1 и с(ab), то са и сb

c=(a*b)*k, kZ

c=a(b*k)=b(a*k)=>ca и cb. Верно и обратное: если ca и cb, то с(ab)

3) Если (а,b)=1, (а,с)=1 и (b,c)=1, то (с, ab)=1

Пусть (с, ab)=d, d1, cd и abd=>a неd и b неd (если d1)=>(a,b)=1

4) Если (a,b)=1, то любые их натуральные степени также взаимно просты. (an,bn)=1.

8. Наименьшее общее кратное

Общим кратным чисел а и b называется число m, ma и mb, m=ОК[a,b].

Число m называется НОК чисел a и b, если: 1. m=ОК[a,b]; 2. Mm, где M=OK[a,b].

НОК определяется с точностью до знака.

Т: НОК чисел а и b определяется формулой

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

Пусть HOД(а,b)=d, тогда а=dk, b=dn, (k,n)=1.

M=OK[a,b], Ma, Mb

M=a*t, M=b*s,

M=dkt, M=dns

dkt=dns, (k,n)=1

k неn, но ktn => tn, t=n*l

M=dknl=a*n*l=ml => Mm => HOK[a,b]

9. Свойства НОК

1) 2а числа имеют НОК. Это следует из того, что число равное всегда для а.

2) НОК целых чисел а,b является наименьшим по величине ОК этих чисел.

3) Если каждое из чисел а,b0 умножить на k, то их НОК тоже умножится на это k. Действительно, m= . Пусть НОД(а,b)=d, тогда , где m-НОК[a,b].

4) аналогично, если каждое из чисел а,b разделить на k0, то их НОК=m, также разделится на это число.

5) НОК взаимно простых чисел равно их произведению. а, b0; (a,b)=1; HOK=m=

6) Если НОК[a,b]=m1, a HOK[m1,c]=m, то НОК[a,b,c]=m

10. Простые и составные числа

Натуральное число p>1 называется простым числом, если оно имеет ровно два делителя 1 и р.

Натуральное число n>1 называется составным числом, если оно имеет больше 2х делителей, т.е. оно делится по крайней мере на одно число не равное 1 и n.

1 - не относится ни к простым, ни к составным числам.

Среди простых чисел существует только одно четное (2), все остальные нечетные.

Свойства:

1) Если простое число рn и n1, то p=n.

Действительно, если предположить, что рn, тогда р имеет три делителя 1, р,n. А это означает, что р - составное, что противоречит условию => p=n

2) Если р1 и р2 различные простые числа, то р2 нер1 и р1 нер2.

Действительно, предположить противное, т.е. деление возможно, а это значит что простые числа р1 и р2 имеют по 3 делителя, чего быть не может.



11. Простые и составные числа

Натуральное число p>1 называется простым числом, если оно имеет ровно два делителя 1 и р.

Натуральное число n>1 называется составным числом, если оно имеет больше 2х делителей, т.е. оно делится по крайней мере на одно число не равное 1 и n.

Свойства:

3) Всякое натуральное число n>1 делится по крайней мере на одно простое число.

Докажем методом мат.индукции:

n>1, n=2, n2 - верно.

Предположим, что для всех натуральных чисел до (n-1) включительно это верно.

Если n-простое число, то утверждение верно.

Если n-составное, то можно представить n=n1*n2; n1,n2<n. По предположению для чисел n1 и n2 наше св-во выполняется, т.е. они делятся на простое число, а следовательно и n.

4) Если n-натуральное число, р-простое, то либо nр, либо (n,p)=1, n1.

Пусть (n,p)=d, тогда nd и pd => d=1, p=d.

Если d=1, то (n,p)=1,а если d=p, то np.

5) Если произведение 2х или более натуральных чисел делится на просто число р, то хотя бы один из сомножителей делится на р.

Пусть (a*b)p => ap или b. Если ар, то теорема доказана.

Пусть а не р, тогда (а,р)=1, х, у =>

ах+ру=1 (*b)

(ab)x+pby=b - все делится на b.



12. Основная теорема арифметики (существование)

Т: Всякое натуральное число n>1, либо простое число либо представима и притом единственным образом в виде произведения простых чисел.

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

Пусть теорема выполняется для всех натуральных n до k включительно (n=k). Докажем справедливость теорема и для числа k+1.

Если k+1 - простое, то теорема выполняется.

Если k+1 - составное, то его можно представить в виде

k+1=m*t; m,t?N; m,t<k+1

Если m и t-простые, то k+1=t*m

Если m и t-составные, то m=m1*m2*…*mk ; t=t1*t2*…*ts; где mi, ti -простые, i=1…k; i=1…s =>

K+1=m1*…*mk*t1*…*ts

Согласно принципу мат.индукции данная теорема справедлива для любого натурального числа n.

13. Основная теорема арифметики (единственность)

Т: Всякое натуральное число n>1, либо простое число либо представима и притом единственным образом в виде произведения простых чисел.

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

Докажем единственность разложения n=m1*…*mk*t1*…*ts

Предположим противное.

n=t1*t2*…*tm; n=p1*p2*…*ps; ti, pi - простые числа.

t1*t2*…*tm= p1*p2*…*ps

(t1*t2*…*tm)р1 => tip1

Пусть t1p1 - простые => t1=p1

(t1*t2*…*tm)р2, t2p2 => t2=p2 и т.д. до последнего множителя ps. Получим что s=m и всякое рi=ti, а это означает, что разложение натурального числа на простые множители единственно.

14. Бесконечность множества простых чисел

Т (Евклида): Множество простых чисел бесконечно.

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

Предположим, что множество простых чисел конечно. Т.е. множество состоит из р1,p2p2,…,pk. Составим произведение этих простых чисел: p1*p2*…*pk.

Запишем число n=p1*p2*…pk+1

Если n-число составное, то оно имеет один простой делитель, т.е. nрi, i=1…k.

Пусть np1, тогда и произведение делится на р1 => 1p1

Получается, что n>pk и не делится ни на одно простое число => n явл.простым числом, причем большим любого простого числа в данном множестве => наше предположение о конечности множества не верно.

15. Теорема об интервалах

Т: Существует сколь угодно большие интервалы, не содержащие простые числа.

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

Возьмем m и построим числа следующего вида: n!+2, n!+3, n!+4,…,n!+n. мы получили интервал подряд идущих составных чисел. В этом интервале нет ни одного простого числа.

16. Решето Эратосфена

Для определения простых чисел, на заданном числовом отрезке, существует метод, называемый решето Эратосфена: на данном числовом отрезке вычеркиваются все числа кратные 2, затем 3, затем 5, 7 и т.д. до наибольшего простого числа р, не превосходящего наибольшего из чисел отрезка. В результате этих действий останутся простые числа.

17. Числовые ф-ии. Ф-ия числа всех натур. делителей числа n

Функции, заданные на множестве натуральных чисел, называются числовыми функциями. К ним относятся: ф(n)-число всех натуральных делителей числа n; д(n)-сумма всех натуральных делителей числа n; ?(n)-число натуральных чисел меньших n и взаимно простых c n.

Т: Если каноническая запись числа n имеет вид , то функция числа всех натуральных делителей числа n равна:

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

Известно, что любой делитель числа n= имеет вид: , где li=0…ki; i=1…m.

Таким образом, следует, что показатель li принимает ровно ki+1 значений, т.е. 0

l1k1+1

l2k2+1

…………

lmkm+1

Таким образом, число набора всевозможных показателей канонического разложения числа n определяет число делителей числа m.

18. Числовые ф-ии. Ф-ия суммы всех натуральных делителей числа n

Функции, заданные на множестве натуральных чисел, называются числовыми функциями. К ним относятся: ф(n)-число всех натуральных делителей числа n; д(n)-сумма всех натуральных делителей числа n; ?(n)-число натуральных чисел меньших n и взаимно простых c n.

Т: если каноническое представление числа n имеет вид , то сумма всех делителей числа n равно:

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

Пусть

Рассмотрим произведение сумм:

Если раскрыть скобки в этом произведении, то получим сумму выражений: , где

А это сумма всех натуральных делителей числа n, т.к. каждое произведение входит в сумму только 1 раз. Заметим, что в записанном исходном произведении стоят суммы геометрических прогрессий со знаменателем р1, р2,…, рm, т.к. , то



19. Мультипликативные функции

Числовая ф-ия Q(n) называется мультипликативной, если выполняются 2 условия: 1)Q(1)=1; 2)Q(m*n)=Q(m)*Q(n), где m и n-произвольные взаимно простые натуральные числа.

Т: Если (n1,n2,…,nm)=1, то Q(n1*n2*…*nm)=Q(n1)*Q(n2)*…*Q(nm), где Q(n)-мультипликативная ф-ия.

Следствие: если каноническая запись числа n имеет вид , Q(n)-мультипликативная ф-ия, то Q(n)=

20. Систематические числа. Непозиционные СС

Для записи натуральных чисел используют различные СС: позиционные и непозиционные.

В непозиционных СС значение каждого применяемого знака не зависит от его места в записи числа. В настоящее время известна и сохранила свое применение непозиционная система римской нумерации. I-1, V-5, X-10, L-50, C-100, D-500, M-1000.

К непозиционным СС относятся византийская(Др.греческая) и СС Др. Руси, которая много взяла от византийской.

В др.греческой СС цифры десятичной системы от 1 до 9 обозначались первыми 9 буквами алфавита: 1=б, 2=в, 3=г….

Десятки обозначались следующими 9 буквами: 10=i. И последние 9 для обозначения сотен.

В др.руси цифры также обозначались буквами, над которыми ставился специальный знак(титла). 10 тыс=тьма; 10 тем=легион; 10 легионов=леодр.



21. Систематические числа. Позиционные СС

Для записи натуральных чисел используют различные СС: позиционные и непозиционные.

В позиционных СС значение применяемых символов зависит от места, которое они занимают в записи числа. Чаще всего применяют позиционные СС с фиксированным образованием и применяют для записи чисел конечное множество знаков. При этом сдвиг цифры на одно место влево влечет за собой ее увеличение в д-раз, где д?N, д>1.

д-основание СС. Чаще всего используют 10-ную СС.

Систематической записью натурального числа N по основанию д называют , где an, … ,a1, a0=0,1,2,…,д-1, an0

Позиционная система с основанием д называется д-ичной СС.

Всякое натуральное число N может быть единственным образом представлено в виде систематической записи по любому основанию д>1.

При записи числа полезно знать формулу определения коэффициента при данной степени д: дк;

22. Переход от одной СС к другой

Данный переход решает 2е задачи:

1) Пусть дана д-ичная запись числа N

N=anдn+…+a1д+a0

Найдем 10-ную запись этого числа.

2) Пусть дана 10-ная запись числа N. Найдем д-ную запись.

Чтобы решить 1ую задачу достаточно поставить 10-ную запись числа ai и д и выполнить указанные действия.

Пример: 38517=3*73+8*72+5*71+1*70=1457

Решим 2ую задачу: для этого число N разделим на д, остаток от деления дает последнюю цифру числа n. Затем частое делим на д, остаток дает предпоследнюю цифру записи числа n. Продолжая процесс деления найдем все цифры.

23. Конечные непрерывные (цепные) дроби

Пусть

Число t можно представить в виде дроби особого вида. Для представления числа t используют алгоритм Евклида.

a=bq0+r1

b=r1q1+r2

Такое представление рационального числа называется конечной цепной или непрерывной дробью. Числа q0, q1,…, qn - неполные частные .

q0?Z, qi?N, i=1,…,n.

Если >0,то q0?N, при а>b; q0=0,при а<b.

Если <0,то q0=-l

Если =с, то с=[c]



24. Теорема о представлении рационального числа в виде конечной цепной дроби

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

Из однозначности нахождения неполных частных следует, что представление рационального числа в виде непрерывной дроби, такой что последнее неполное частное отлично от 1, единственно.

Т: всякая конечная цепная дробь есть рациональное число. Для док-ва этой теоремы достаточно произвести указанные арифметические действия над 1, q0, q1,…,qn. В результате получим рациональное число.

Пример:

25. Подходящие дроби. Свойсва(1,2)

Пусть дано

Дроби называются подходящими дробями цепной дроби.

Числитель и знаменатель подходящей дроби:

Формула для нахождения дроби любого порядка:

Свойства:

1) Числители и знаменатели подходящих дробей - целые числа. Причем знаменатели натуральные числа и образуют возрастающую последовательность.

2) Числители и знаменатели 2х соседних подходящих дробей связаны соотношением

26. Подходящие дроби. Свойства(3,4)

Пусть дано

Дроби называются подходящими дробями цепной дроби.

Числитель и знаменатель подходящей дроби:

Формула для нахождения дроби любого порядка:

Свойства:

3) Подходящие дроби несократимы. НОД(Pk,Qk)=1

4) Подходящие дроби четного порядка образуют возрастающую, а нечетного - убывающую последовательность.

27. Подходящие дроби. Свойства(5-8)

Пусть дано

Дроби называются подходящими дробями цепной дроби.

Числитель и знаменатель подходящей дроби:

Формула для нахождения дроби любого порядка:

Свойства:

5) Каждая подходящая дробь меньше подходящих дробей

6) Любая подходящая дробь четного порядка меньше любой подходящей дроби нечетного порядка.

7) Пусть t>0, тогда при его разложении в непрерывную дробь, четные подходящие дроби - это приближение по недостатку, а нечетные подходящие дроби - по избытку.

8) Если t>0(положит.рацион.число), - подходящая дробь в его разложении, то

28. Свойства сравнений, не зависящих от модуля(1,2,3)

1) Отношение сравнения явл. отношением эквивалентности в кольце целых чисел, т.е. отношение сравнения рефлексивно, транзитивно, симметрично.

Доказательство: Из определения сравнения 2х целых чисел следует, что . Следовательно, отношение сравнения рефлексивно.

Если ; , т.е. симметричность выполняется.

Пусть и , тогда и - транзитивность выполняется.

2) Сравнение по одному и тому же модулю можно почленно складывать.

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

Докажем, что a+с(b+d)(mod m)

a+c-(b+d)=(a-b)+(c-d)сумма тоже m

3) Два сравнения по одному и тому же модулю можно почленно вычитать.

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

Докажем, что a-с(b-d)(mod m)

(a-c)-(b-d)=a-c-b+d=(a-b)+(d-c)сумма тожеm

29. Свойства сравнений, не зависящих от модуля(4,5,6)

4) К обеим частям сравнения можно прибавлять одно и то же целое число.

Док-во: ; (a+t)(b+t)(mod m); a+t-b-t=a-b(a+t)(b+t)(mod m)

5) Сравнение по одному и тому же модулю можно почленно перемножать.

Доказательство: Пусть ; . Докажем, что acbd(mod m), т.е. (ac-bd)

(ac-bd)=ac-bd-bc+bc=c(a-b)+b(c-d).

6) Обе части сравнения можно умножать на одно и то же целое число.

Доказательство: . Докажем, что , т.е. (at-bt)m.

at-bt=t*(a-b)

30. Свойства сравнений, зависящие от модуля(1,2)

1) Если и mn, то .

Доказательство: Действительно, если (a-b)m и mn(a-b)n

2) Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.

Доказательство: Пусть , т.е. a-b=mt, t?Z, ac-bc=mtc, ac-bc=(mc)tacbc(mod mc).

31. Свойства сравнений, зависящие от модуля(3)

3) Пусть дан многочлен f(x) с целыми коэффициентами. Тогда если , то f(a)f(b)(mod m).

Доказательство: Действительно, пусть

+…………………….

____

f(a)f(b)(mod m)

32. Класс вычетов по модулю m

Все множество целых чисел можно разбить на n-непересекающиеся … в зависимости от деления на число m. Известно, что при делении на целое число m получаются остатки 0,1,2,…, m-1. Совокупность всех целых чисел, которые делятся на m, обозначим , которые дают остаток 1 обозначим , …, , получим m подмножеств, которые попарно пересекаются. Каждое такое подмножество называется классом вычета по модулю m.

a, b-принадлежат одному классу вычетов; (a-b)m

верно и обратное: если (a-b)m, то они принадлежат одному классу вычетов по модулю m.

Все множество классов вычетов - Zm.

Классы вычетов можно складывать и умножать. Чтобы сложить 2а класса вычетов а и b нужно взять по представителю из каждого класса, найти сумму с, а затем найти класс, который содержит это число с. Аналогично с умножением.

При выполнении операции «» нейтральный элемент - , а при «+» - . Операции «» и «+» -ассоциативны, коммутативны; операция «» дистрибутивна относительно «+». .

Таким образом, множество всех классов Zm с операциями «+»и «»образуют коммутативное кольцо с 1. Его называют кольцом вычетов по модулю m.

33. Полная система вычетов. Свойства (Т1.)

Рассмотрим кольцо классов вычетов по модулю m. Выберем из каждого класса по одному представителю. Пусть это будут числа х1, х2, … ,хn. Полученную совокупность называют полной системой вычетов по модулю m. Т.к. в каждом классе вычетов содержится бесконечно много целых чисел, то можно записать и бесконечное число различных полных систем.

Среди полных систем вычетов наиболее часто используются следующие: 1)ПС наименьших неотрицательных вычетов; 2)ПС наименьших положительных вычетов; 3)ПС абсолютно наименьших вычетов-в этом случае из каждого класса берется наименьший по абсолютной величине вычетов.

Т: Любая совокупность {х1, х2,…, хn} попарно несравнимых по модулю m образует полную систему вычитов по модулю m.

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

1) Очевидно, что каждое из записанных чисел принадлежит некоторому классу вычетов по модулю m.

2) Т.к. числа не сравнимы попарно между собой по модулю m, то все они принадлежат разным классам вычетов по модулю m.

3) Всего классов вычетов по модулю m - m. И чисел у нас m.эта совокупность представляет каждый класс вычетов, т.е. явл. полной системой вычетов по модулю m.

34. Полная система вычетов. Свойства (Т2)

Рассмотрим кольцо классов вычетов по модулю m. Выберем из каждого класса по одному представителю. Пусть это будут числа х1, х2, … ,хn. Полученную совокупность называют полной системой вычетов по модулю m. Т.к. в каждом классе вычетов содержится бесконечно много целых чисел, то можно записать и бесконечное число различных полных систем.

Среди полных систем вычетов наиболее часто используются следующие: 1)ПС наименьших неотрицательных вычетов; 2)ПС наименьших положительных вычетов; 3)ПС абсолютно наименьших вычетов-в этом случае из каждого класса берется наименьший по абсолютной величине вычетов.

Т: Пусть числа (а, m)=1, b - произвольное целое число. Тогда если (1)х1, х2,…,хn - полная система вычетов, то и совокупность (2)ax1+b, …,axm+b - полная система вычетов по модулю m.

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

1) Рассмотрим числа совокупности (2), т.к. это целые числа, то каждый элемент ? …

2) Покажем, что любые 2а числа axi+b и axj+b несравнимы по модулю m.

3) Предположим, что они сравнимы:



Получили противоречие. Следовательно, система (2) - это система целых чисел попарно несравнимых по модулю m.

По теореме 1 всякая система m-целых чисел попарно несравнимых по модулю образуют полную систему вычетов по модулю m.

35. Теорема об остатках

Т: Пусть m и n - взаимно простые числа, тогда для любых классов вычетов найдется класс вычетов , такой что х? тогда и только тогда, когда х?.

Доказательство: Выберем в классе наименьший положительный вычет а. Расположим наименьшие положительные вычеты по модулю m*n в виде прямоугольной таблицы

1 2 3 …. m

m+1 m+2 m+3 …. 2m

2m+1 2m+2 2m+3 …. 3m

………………………………………….

(n-1)m+1 (n-1)m+2 (n-1)m+3…. n*m

Тогда числа im+a, где i=0, …, n-1; и только они сравнимы с а(mod m). Но эти же числа образуют по лемме полную систему вычетов по модулю n, т.к. i=0, …, n-1. Поэтому среди этих чисел найдется хотя бы одно число, принадлежащее классу . Верно и обратное, если класс существует, то найдется число х?.

36. Приведенная система вычетов

Т: Числа одного и того же классов вычетов по mod m имеют с m один и тот же НОД, т.е. , то НОД(а,m)=НОД(b,m).

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

(a,m)=(b,m)

НОД mod m и любого числа а из данного класса вычетов по mod m, называется НОД mod m и данного класса.

Класс называется взаимно простым с mod m, если НОД этого класса с m равен 1.

Совокупность вычетов по mod m, взятых по одному из каждого взаимно простого с m классов вычетов по mod m, называется приведенной системой вычетов.

37. Делители нуля в кольце вычетов Zm

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

Т: Если НОД(m, ); ?Zm , то класс является делителем 0 в кольце вычетов Zm.

Доказательство: (m, )=d, d

Выберем а?, тогда (m,a)=d, d

Тогда, a=dx, m=dy, (x,y)=1

Очевидно, что m>d>0, поэтому

ay=dxy=mx

(ay)

- делитель 0.

Следствие: любой класс вычетов в кольце Zm является либо нулевым, либо делителем нуля, либо обратимым в Zm. Действительно, если



38. Функция Эйлера

*Ф-ей Эйлера называется числовая ф-ия, которая определяет число классов вычетов по mod m взаимно простых с этим модулем.

*Ф-ей Эйлера называется числовая ф-ия, которая определяет число натуральных чисел, не превосходящих m и взаимно простых с m.

Из определения следует, что ф-ия Эйлера определяет число элементов в приведенной системе вычетов по mod m.

Определим способы вычисления ф-ии Эйлера ?(m).

Если m=1, то кольцо классов вычетов состоит из одного класса ; Если НОД(1,1)=1, то принято считать, что ?(1)=1

Если m=p, p - простое число, тогда ?(m)=?(р)=р-1

Если

39. Теоремы Эйлера и Ферма

Т(Эйлера): Если целое число а взаимно просто с m, то .

Док-во: т.к. (а,m)=1, то коммутативная группа обратимых элементов кольца Zm.

Любой элемент группы Рm,т.е. класс , порождает подгруппу, порядок которой является делителем числа элементов в группе Рm, а это число элементов есть ?(m).

Порядком подгруппы называют такое натурально число s, что .

Пусть ?(m)=s*t

.

Т(малая теорема Ферма): Если р - простое число, а - произвольное целое число и (а,р)=1, то ар-11(mod p).

Док-во: Из теоремы Эйлера>, -целое.

Тогда при m=p, , .

Очень часто применяют следствие из малой теоремы Ферма, хотя ее бывает называют просто теоремой Ферма: ара(mod p)..

40. Корни сравнения

Пусть f(x) - многочлен с целыми коэффициентами.

Решить сравнение - значит найти все целые значения х, такие, что f(x) и ?(x) принимают целые значения и их разность делится на m.

Если х=с удовлетворяет сравнению, т.е. f(c)?(c)(mod m), c?Z, то с - корень сравнения.

Т: если число с удовлетворяет сравнению f(c)?(c)(mod m), то и любое целое число с1, удовлетворяющее условию сс1(mod m), удовлетворяет сравнению f(х)?(х)(mod m).

Доказательство: по условию f(c)?(c)(mod m)>(f(c)- ?(c))m

f(c)- ?(c)

f(c1) ?(c1)(mod m) - по св-ву сравнения.

Следовательно, с1 - удовлетворяет сравнению f(х)?(х)(mod m).

Из доказанной теоремы следует, что если целое число с удовлетворяет данному сравнению, то и все числа из класса вычетов , удовлетворят данному сравнению.

Таким образом, решить сравнение f(х)?(х)(mod m) - это значит найти класс вычетов по модулю m, любое число которого удовлетворяет сравнению. Из этого определения следует один из способов решения. Это метод проб: записать полную систему вычетов, подставлять поочередно все числа из системы в сравнение.

41. Равносильность сравнений с одним неизвестным

*Сравнения f1(х)?1(х)(mod m) и f2(х)?2(х)(mod m) называются равносильными, если множество их решений совпадает

Т: если в сравнении заменить на числа сравнимые с ними, то полученное сравнение будет равносильным.

*xn *xn-1 ……………. *x *x0	………….

Степенью сравнения называется наивысший показатель степени, коэффициент при котором не делится на m.

Сравнение, у которого все коэффициенты делятся на m, рассматривается как не имеющее степень.

42. Неопределенные уравнения

Одно ур-е с несколькими неизвестными, имеет как правило бесконечное кол-во решений, поэтому такие уравнения называют неопределенными.

Рассмотрим вопрос о нахождении целочисленных решений.

aх+by=c; a,b,c?Z.

будем считать, что а,b

пусть х0, у0 - частное решение этого ур-я. Тогда имеем место равенство ах0+by0=c

ax0-c=-by0

если (x0,y0)-частное решение, то ах0с(mod b).

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

Если ах0с(mod b), то (ax0-c), y0?Z

ax0-c=b (*-y0)

ax0+by0=c

(x0, y0)-частные решения.

Если х0,у0 - целочисленное решение неопределенного ур-я ах+by=c, где а,b,с?Z; a,b, то х0-решение сравнения ax0c(mod b). Верно и обратное утверждение, т.е. если х0-решение сравнения ax0c(mod b), то у0, что х0,у0 являются решением неопределенного ур-я ах+by=c.

Т: Если НОД(а,b)=d, то ур-е ах+by=c имеет решение тогда и только тогда, когда с.

Т: если известно решение (х0,у0) неопределенного ур-я ах+by=c и НОД(а,b)=d, то общее решение неопределенного ур-я имеет вид:

, t?Z

43. Порядок классов вычетов по заданному модулю

Гm-группа, Zm-кольцо.

*Порядком класса вычетов взаимно простого с модулем m называется наименьшее натуральное число, такое что

Число б называется также порядком всех чисел, входящих в класс вычетов . Таким образом, если а?, .

*Если (a,m)=1, то порядком числа а(mod m) называется наименьшее натуральное число б, б?N, aб1(mod m).

Т: если порядок класса вычетов , равен б, то , тогда и только тогда, когда .

С1: если порядок класса вычетов , равен б, то , тогда и только тогда, когда .

С2: если порядок класса вычетов , равен б, то попарно различны.

44. Первообразные корни

Пусть р - простое число, просмотрим группу обратимых элементов кольца Z(mod p). Это будут классы . Причем порядок каждого из этого класса вычетов является делителем числа р-1.

*Первообразным корнем по простому модулю р называется класс вычетов , порядок которого равен р-1.

Из определения следует, что если -первообразный корень по модулю р, то тогда и только тогда, когда (s-t)(p-1)-на основании предыдущих теорем.

Если д-первообразный корень по mod p, то все классы вычетов попарно различны.

Т: если д-первообразный корень по простому модулю р, то для любого ненулевого класса найдется в, такое, что . Таким образом, если р>2 и р-простое число и , то количество классов вычетов по модулю р, имеющих порядок в, равен ?(в).

45. Свойства приведенной системы вычетов

Т: Пусть число классов вычетов взаимно простых с m равно к, тогда любая совокупность к-целых чисел х1,х-2…хк попарно несравнимых по модулю m и взаимно простых с m представляет собой приведенную систему вычетов по модулю m

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

1. Очевидно, что все числа совокупности х1,х-2…хк принадлежат некоторым классам вычетов по модулю m, т.к. эти числа несравнимы по модулю m, то они принадлежат различным классам вычетов

2. По условию, каждое из чисел взаимно просто с m, следовательно, они принадлежат классам вычетов, которые взаимно просты с m

3.По условию классов вычетов, взаимно простых с m, к и чисел в совокупности к, следующая совокупность х1,х-2…хк это приведенная система вычетов по модулю m. ч.т.д.

Пр. полная система вычетов для m=12 1,2,3,4,5,6,7,8,9,10,11,12, приведенная же, это все из вышеперечисленных, которые взаимнопросты с m: 1,5,7,11



46. Мультипликативная группа обратимых эл.

Zm {0,1,2….m-1}

Т: Для того, чтобы класс вычетов а был обратимым необходимо и достаточно, чтобы а был взаимно прост с m

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

1. Пусть (а, m)=1, выберем в а число а, тогда (а,m)=1, тогда по свойствам НОД найдутся х,у, что ах+mу=1, отсюда:

ах-1=-my, т.е. (ах-1):m>ах?1 (mod m)

х, хх, а*х=1, х Zm

х = а-1 это значит, что класс а обратим

2. Пусть а - обратим, тогда

а *х=1

ах?1 (mod m)

ax-1 = my, y Z. ч.т.д.

Таким образом, в кольце Zm каждый класс, взаимнопростой с m, обратим.

Множество Рm замкнуто относительно умножения, ассоциативно и коммутативно, 1 Рm т.к. он обратим и каждый элемент Рm имеет себе обратный по определению. Эту группу по умножению называют мультипликативной группой элементов в кольце Zm.

47. Свойства мультипликативной группы Рm

1. Если а и в по модулю m взаимно просты с m, то класс а * в тоже взаимно прост с m.

Действительно, если классы а и в взаимно просты с m, то они обратимы и принадлежат Рm, т.е а * вРm то оно обратимо, то этот класс а * в взаимно прост с m.

2. Если а, а Z взаимно прост с m, то существует единственный класс в, такой что а * в = 1. Этот класс в взаимно прост с m, при этом обратный а и обозначается как а-1.

По свойствам группы Рm каждый элемент имеет обратный, когда а * в = 1, причем в- единств.

3. Если а взаимно прост с m и 2 различных класса х и у Zm взаимно просты с m, то ах ? ау

4. Пусть группа Рm состоит из классов вычетов

(1) Рm : х1,х-2…хк и а Рm, тогда

(2) ах1,ах-2…ахк так же являются классами вычетов в группе Рm, только записанными в другом порядке

Действительно, классов вычетов (2) ровно к, столько же, сколько в Рm, если ахi = ах-j > хi = хj поэтому (1)и(2) совпадают

Из 4 следует, что приведенная система вычетов ах1,ах-2…ахк где а взаимно просто с m образуют приведенную систему вычетов по модулю m

Размещено на Allbest.ru

...