aaki=ai(m) – для каждого i
a1=aak1(m)
a2=aak2(m)
….
am=aakm (m)
a1a2…am=am(ak1, ak2,.. akm)(m) => am=1(m) m=j(m)
т.е. aj(m)=1(mod m)
Следствие:
Если p- простое, то
aj(p)=1(mod p)
ap-1=1(p)
ap=1(p) – то что доказал Фермаb
Решение сравнений в первой степени.
x2=1(mod 8)
ax=b(mod m) – сравнения первой степени.
х0 – единственное решение х0+tm – тоже решение.
Теорема: 19
d=D(a,m) для того, чтобы сравнение решение было, нужно, чтобы b||d
x0, x+m/d, x0+2m/d,…,x0+(d-1)m/d
Доказательство:
ax=b(mod m) (ax-b)/m ax-b||m т.е. существует
y – такое, что ax-b=my => ax-my=b – Диафантово уравнение когда D(a,m)||b т.е. d||b и все решения
x=x0+(m/d)t
т.е. всего различных классов вычетов d
Пример:
38x=4(26)
m/d=13
38x-26y=4
19x-13y=2
x0=-4 => x0=-4(26) x1=9(29) – два класса вычета.
2-й способ решения сравнений на основе теоремы Эйлера-Ферма.
ax=b(m) D(a,m)=1 a,b,m можно ||d
aj(m)=1(mod m) умножим на b
aj(m)b=b(m)
a (aj(m)-1b)=b(m) => x=(aj(m)-1b)
Пример:
11x=15(24) D(24,11)=1 15||1
j(m)=23 3=24((2-1)/2)((3-1)/3)=24.2/6=8
x0=117.15(mod 24)
112=1(mod 24)
116=1(mod 24)
117=11(mod 24)
117.15=165(mod 24)=-3(24)
Теорема: Вильсена
P – простое число тогда и только тогда, когда (p-1)!+1||p
Доказательство:
1) p – простое число
Докажем (p-1)!+1||p
Для p>3
a не кратно p т.е. D(a,p)=1, тогда ax=1(p) и имеет ровно 1 класс т.к. D(a,p)=1=d
d – решений, т.к. d=1 => 1 решение.
x=b(p) – класс решений,
b принадлежит {1,2,3…(p-1)}
тогда а принадлежит одному из классов т.е. для любого b есть а, такое что ab=1(p).
Если a=b, тогда a2=1(p)
(a-1)(a+1)||p, отсюда a=1(p) или a=-1(p)
a=b тогда если а=1, либо a=p-1, для всех остальных а¹b
Возьмем все эти сравнения и перемножим
2.3.4…(p-a)=1(p) до множим (p-1)=-1(p) =>
(p-1)!+1||p
A=>B ó не B=> не A
Если из A следует В, то из не В следует не А
Тогда если (p-1)!+1||p то p простое =>
Если p – не простое, тогда (p-1)!+1 не кратно p
P – составное, тогда D(p-1)!,p)>1=d, тогда (p-1)!+1 не кратно p т.к. единица, должна быть кратна d.
т.е. p – простое.
Китайская теорема об остатках
x1=c1(m1) D(mi,mj)=1
x2=c2(m2) есть набор взаимнопростых mi,mj
…. И есть остатки х от деления на mi,mj
xk=ck(mk)
<x>m1=c1 C1 C2 Ck код числа
<x>m2=c2
…
<x>mk=ck
т.е. существует решение x и все сравнения лежат в классе вычетов по модулю (m1,m2,…mk)
Докажем, как по китайскому коду восстановить число
c1=0; c2=2; c3=3;
m1=3 ; m2=5 ; m3=8;
M=m1m2m3=120
M1= m2m3=40 M1x1=1(3) 40x1=1(3) x1=1
M2= m1m3=24 M1x1=1(5) 24x1=1(5) x1=4
M3= m1m2=15 M1x1=1(8) 15x1=1(8) x1=7
x=Si=13((xiMi)ci)=40.0.1+24.4.2+15.3.7=507(120)=27(120)
Многочлены
Pn(x)=a0+a1x+a2x2+…+anxn=Si=1n((aixi)
aiÎQ,R,C
an¹0, то deg Pn=n an=1
Теорема: 22 О делении с остатком
" Pn(x), Qm(x)
Существует единственное Rn-m(x) и Sm-1(x): Pn(x)=Qm(x).Rn-m(x)+Sm-1(x)
Deg Sm-1(x)<=m-1
Доказательство:
Qm(x), n=deg Pn(x)
n<x
база: Pn(x)=Qm(x).0(x)+Sm-1(x)
индукционный переход:
`Pn-1(x)=Qm(x) `Rn(x)+`Sn(x)=>
Pn(x)=Qm(x).Rn-m(x)+Sm-1(x)
(Rn-m(x)-`Rn-m(x))Qm(x)=(Sm-1(x)-`Sm-1(x)) справедливо если Rn-m(x)=`Rn-m(x) иначе противоречие.
Pn(x)=a0+a1x+a2x2+…+anxn
Qm(x)=b0+b1x+b2x2+…+bmxm
Pn(x)=Qm(x).Rn-m(x)+Sm-1(x)
Rm(x)=z0+z1x+z2x2+…+zn-mxn-m
Sm(x)=s0+s1x+s2x2+…+sm-1xm-1
S1 k=n-m
S2 Zk=am+n/bm
aj=aj-Zkbj-k
j=m+k-1, m+k-2,…,k
S3 k=k-1 if (k>=0) goto S2
Else stop
Pn(x)=Qm(x).Rn-m(x)+Sm-1(x)
Sm-1=0 => Pn(x)||Qm(x)
Наибольший общий делитель
НОД для Pn(x) и Qm(x) это многочлен наибольшей степени общих делений Pn(x) и Qm(x).
D(Pn(x),Qm(x))
Алгоритм Евклида для 2-х многочленов
D(P1(x),P2(x))
P1(x)=P2(x) Q1(x)+R1(x)
deg R1(x)<deg P2(x)
P2(x)=R1(x) Q2(x)+R2(x)
deg R2(x)<deg R1(x)
R1(x)=R2(x) Q3(x)+R3(x)
deg R3(x)<deg R2(x)
……..
Rn-2(x)=Rn-1(x) Qn(x)+Rn(x)- НОД
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.