matematika Elementárna teoria čísiel

1.Veta o delený zo zvyškom ak n є N, tak existujú jednoznačne určené čísla q,r єZ, že platí n=q.m+r a 0≤v< m
Dôkaz {k;k.m≤n} 0≤{k;k.m≤n} - ohraničená množina
q= max{k;km≤n} => qє{k;km≤n}=>q.m≤n=>n=q.m+r
môže nastať r≥m=>r=m+r1≥0
n=qm+m+r1=(q+1)m≤n spor s maximál. q
rє{0,...,m}
nech n=q1m+r1 0≤r1 n=q2m+r2 0≤r2q1m+r1-q2m+r2 ak q1>q2=>q1≥q2+1=>
q1m+r1≥(q2+1)m+r2=q2m+m+r1≥q2m+m>q2.m1+r2
nech q1≠q2
q1>q2=>q1>q2+1Vq1m>(q2+1).m=>n-q1m+r≥(q2+1)m=
=q2m+m+r1≥q2m+m>q2m+r2-n n>n / spor.
Q1-q2=>q1m=q2m
r1=r2
2. Princíp mat. indukcie
V(n) V(n) =>V(n+1)
V(1) V(1) =>V(2) =>V(3)
Nech n0 je najmenšie prir. Číslo, že V(n0)- neplatí
V(n0-1) to platí
V(n0-1) =>V(n0+0)
3. Deliteľnosť Ak a,b єZ tak hovoríme, že a je delitelom b <=> kєZ i b=k.a
Nech A,B,CєZ potom
a)ak a/b Λ b/c =>a/c
b)ak a/b Λ a/c =>a/b+c
c)ak a/b Λ b/a=>a= ±b
Dôkaz
a)a/b=>b=k.a
b/c=>c=k´.b c=k.k´.a, c=k´´.a =>a/c
b)b=k.a c=k1.a b+c=k.a+k1.a=(k+k1).a=>a/b+c
c)a/b=>b=k.a
b/a=>a=k2.b
b=k.k2.b
b=0=>a=0 0=±0
b≠0=>1=k.k2 k=±1;k=±1
a=±b
Prvočísla=>priamkové čísla, zlé zlomky
def.číslo nєN nazyvame prvočíslom <=>p>1~ d/p=>d=1 v d=p
Prvočíslo je číslo ktoré je deliteľ sám so sebou alebo 1. Existuje ich nekonečne veľa.
V1nech nєN a n >1, potom mini{d,d>1^ d/h}je prvočíslo. Dôk. Nech p=min{d;d>1^d/h} p=najmenší netrivialny delitel, nech p nieje prvočíslom potom existuje d>1;dd/n
Spor s minimalitou p
V2 existuje nekonečne veľa prvočísel
Dôk. nech p1,...,pn; sú prvočísla
A=p1,p2,...,pn+1
P=min{d,dІA ^d>1} =>p je prvočíslo pІp1,p2,...pn+1
Ak by p=p1=>p1Іp1,p2,...pn+1- p1...pn=1- spor.
p≠p1,p2,...,pn
5.

Ak a,b,cєZ, tak ax+by=c, kde x,yєZnazyvame lineárna diofantická rovnica
a)ak d=(a,b), ak ax+by=c má riešenie, tak d/c
b)ak b/c je riešiteľná
Dôk.d/c=>c=c1.d
ax+by=c1.d
ac1x0+bc1y0=c1(ax0+by0)=c1.d=c
V1.Diofantická rovnica ax+by=c je riešiteľná práve vtedy, ak (a,b)/c
6x+9y=3
2x+3y=1
x=­1, y=1
2x+3y=2(-1)+3.1
2(x+1)=3(1-y) =>2.3t-1+1=>2.3t=3(1-y)
x+1=3t=>x-3t-1
1-y=2t=>2t+1y
6.Základná veta aritmetiky Ak nєN a n>1 tak existuje jednoznačne určené prvočísla p1Dôk.nech n=2=>n=21= rozklad
V(n): každé číslo väčšie ako 1 tak n ma rozklad
V(n): ak mє{1,...,n} m>1tak m má rozklad
V(n+1): ak mє{1,…,n+1}a m >1, tak ma rozklad
V(n) =>V(n+1)
7.Kongurencia ak mєN a a,bєZ a je kongurentné s b modulo m<=>a má rovnaký zvyšok po delení m ako b.
a≡b(mod m)
V1Ak m je prirodzené číslo a a,bєZ, tak a≡b(mod m)
<=>m/b-a
Dôk.dokazujeme ekvivalenciu teda 2 implikácie nech platí a≡b(mod m)
a≡m.q1+r
b≡m.q2+r
a-b=mq1+r-(mq2+r)=mq1+r-mq2-r=mq1-mq2=m(q1-q2)
m/a-b
nech m/b-a, b aj a vydelím so zvyškom
b=mk1+r1
a=mk1+r2
a-b=m(k1-k2)+r1-r2
m/ r1-r2; r1,r2є{0,…,m-1}=> r1-r2=0=>r1=r2=>a≡b(mod m)
V2.Nech n je prirodzené číslo a a1,b1,a2,b2єZ. Ak a1≡b1(mod m) a a2≡b2(mod m), tak a1+a2≡b1+b2(mod m)
a1.a2≡b1.b2(mod m)
Dôk. V1=>m/b1-a1
m/b2-a2
=>m/( b1-a1)+( b2-a2) =>m/b1+b2-(a1+a2) =>a1+a2=b1+b2(mod m)
a1a2-b1b2=a1a2+a1b2-a1b2-b1b2=a1a2-a1b2+a1b2-b1b2=a1(a2-b2)+b2(a1-b1)
m/a1a2-b1b2
a1a2=b1b2(mod m)
V3.Ak a,d,cєZ a mєN tak platí
1,a≡a(modm) – a dáva podelení m taký istý zvyšok ako a
2,a≡b(mod m) =>b≡a(mod m) - triviálme
3,a≡b(mod m) Λ b≡c(mod m) =>a≡c(mod m)-ak a dáva rovnaký zv. podelení m a b dáva po
V4. priprdzené č. je deliteľné 3 práve vtedy, ak jeho ciferný súčet je deliteľný 3.
Dôk.predpok.,že nejaké priroz. č. má takýto rozvoj:
m≡an110n+an-1.10n-1+...+a110+a0
1≡1(mod 3) a0≡a0
101≡1(mod 3) 10.a1≡a1(mod 3)
102≡1(mod 3) 10.a2≡ a2(mod 3)
103≡1(mod 3) 10.a3≡a3(mod 3)
10n≡1(mod 3) 10.an≡an(mod 3)- sčítam a dostanem to č.m => m≡a0+a1+...+an(mod 3) ciferný súčet
8.Prvočísla v aritmetických postupnostiach
V1 Existuje nekonečne veľa prvočísiel v tvare 3k+2
Dôk. Nech p1 až p2 sú všetky prvočísla v tvare 3k+2
p1 =? Tu dá zv.2
A= 3(p2..k.. pn)+2 pr/A=>A≡0(mod p2)
A=q1α1 q2α2...qrαr A≡2 (mod p2)
2≡0(mod pr)
p2/2 spor
gi = 1(mod 3) A nie je deliteľom p2, p3,.. giα1 = 1(mod 3) p2.....pn ┼ A
A = 1 (mod 3) 3┼ A, 2┼ A
Spor sú zvyš.1 A môže byť deliť. pre (3k+1)
Dirichletová veta o zvyškoch ak (a,m)=1, tak existuje nekonečne veľa prvočísiel v tvare a+k.m; existuje ∞ veľa prvočísiel p=a (mod m)
V2 nech mєN a a,d,cєZ
Potom a+c≡b+c (mod m) =>a≡b(mod m)
Dôk. a+c≡b+c(mod m)
-c≡ -c(mod m)
a≡b(mod m)
a,b,cєZ ; mєN ? nie vždy
ac≡bc(mod mň=> a≡b(mod m)
14≡2(mod 12)- pravda
7≡1(mod 12)- nepravda
10≡70(mod 12)/.5- pravda
2≡14(mod 12)- pravda
V3 necha,b,cєZ mєN a (c,m)=1 Potom ac≡bc(mod m) => a≡b(mod m)
Dôk.

ac≡bc(mod m) =>m / bc-ac= c/b-a
m/c(b-a) =>m/b-a =>a≡b(mod m)
9.Úpravy a redukovaný zvyškový systém mod m mєN, tak množinu Zm{0,1,...,m-1}nazyvame úplným zvyškom mod m
V1 ak aєZ a mєN tak existuje rєZm, že a≡r(mod m)
Dôk.Veta o delení so zvyškom a=a1.m+r; rєZm
a≡r(mod m)
nech a≡r1(mod m) r1 єZ
r1≡r(mod m) =>r1=r
Ak mєN, tak množinu Rm={rєZm;(r,m)=1} nazyvame redukovaním zvyškovým systémom mod m
V2 Ak mєZ a (0,m)=1(b,m)=1, tak aj (ab,m)=1
Dôk. ax+my=1 x,yєZ
bx1+my1=1 x1,y1єZ
(ax+my).(bx1+my1)=1
abx x1+axmy1+mybx1+m2yy1=1
abx x1+axmy1+my(bx1+my1)=1
x=x.x1 y=axy1+y(bx1+my1)
ak x+my=1
V3 mєN a r1,r2 єRm. Potom existuje r3єže platí r1.r2≡r3(mod m)
Dôk. (r1;m)=1
(r2;m)=1
(r1,r2,m)=1
r1,r2´mg+r3=>(r3;m)=1=>r3єRm
V4 Ak rєRm, tak existuje práve jedno r´єRm, že platí r,ŕ≡1(mod m)
Dôk. (r,m)=1
ar+bm=1
a=m.q+r´ r´єZm
(m.q+r´)r+vm=1
r´.r+mgr+bm=1=>(r´,m)=1=>r´єRm
r´.r-1=-m.q.r-bm≡0(mpd m)
r´.r ≡1(mod m)
r.r´≡1(mod m)
r.r´1≡r.r´(mod m)
r´1≡r´(mod m)
r´inverzný prvok r mod m, ozmr=1/r (mod m)
10. Eulerová funkcia nєN a n>1 a Rn / redukovaný zvyškový systém tak počet jeho zvyškov označujeme φ(n)= ІRmІ- Eulerová funkcia čísla n
φ(1)=1, φ(6)=2, φ(7)=6, φ(8)=4, φ(9)=6, φ(19)=18, φ(30)=8
Eulerová veta nech mєN a n>1. potom pre každé a єN tak ,že (a,m)=1, platí aφ(m)≡1(mod m)
Dôk. nech Rm={a1….ak}; k=φ(m)
(a,m)=1
(aa1;m)=1
(aa2;m)=1
(aak;m)=1
aa1≡aja(mod m) {aj(1);aj(2),...,aj(k)}єRm
aa2≡aj(2)(mod m)
aak≡ajäk)(mod m)
predpokladáme, že aj(n1)≡aj(n2)
aan1≡aj(n1)(mod m)
aan1≡aj(n2)(mod m)
aan1≡aan2(mod m)
an1≡an2(mod m)
an1≡an2=>n1=n2
teda dokázali sme implikásiu:aj(n1)=aj(n2) =>n1=n2
І{aj(1);...;aj(k)}І=k
{aj(1);…;aj(k)}={a1;…ak}

aa1≡aj(1)(mod m)
aa2≡aj(2)(mod m)
aak≡aj(k)(mod m)
(aa1)...(aak)≡aj(1)...aj(k)(mod m)
aka1...ak≡a1...ak (mod m)
k= φ(m) ak≡1(mod m)
aφ(m)≡1(mod m)
11.Fermatová veta Nech p je prvočíslo. Potom pre každé prirodzené číslo a platí: an≡ a(mod p)
Dôk.

Ak (a,p)=1, porom Eulerová veta => aφ(m)≡1(mod m) 0→je súdelitelmá a každým číslom okrom 1
Φ(n)= p-1 ap-1≡1(mod p)
a ≡a(mod p)
ap ≡a(mod p)
(a,p)>1=>(a,p)=p=>p/a=>a≡0(mod p)
a1≡0(mod p)
ap≡a(mod p)
dok. implikáciou 1p≡1(mod p)
zp=(1+1)=1+(p1)+(p2)+...+(pp-1)+1
(pk)= (p-k)! p!k! 1≤K≤1
(pk)≡0(mod p) (p,k)=1
2p≡2(mod p) )p,p-k)=1
ap≡a(mod m)
(a+1)p=ap+(p1)an-1+(p2)ap-2+...+1≡ap+1(mod p)
(a+1)p≡ap+1(mod p)
(a+1)p≡a+1(mod p)
12.Formula pre Eulerovú funkciu
V. nech nєN a n>1 a n=p1α1,pαα2,...,pαkαk – kanonický rozklad. Potom α(n)=m(1-1/p1)(1-1/p2)...(1-1/pk)
dєN (d,n)=1<=> i=1,…,k:pi+d
d≤n N(d)={klema1ak dІn, tak ІN}d|І=n/d
Dôk.rr=d.r1 d.r1{0,d,2d,…,d(n/a-1)}=N(d) ІN(d)І=n/d
Dôk.ІZnІ=n Rn=Zn – (N(p1))υ...υN(pk))
U(n)=ІRnІ=ZnІ-ІN(p1)υ...υN(pk)І=n-ІN(p1)υ...υN(pk)І
Lema2 ІN(p1)υ...υN(pk)І=∑ІN(pk)І - ∑ІN(pi)∩N(pj)І +∑ІN(pi)∩N(pj)∩N(pr)+...+(-1)m+1 ∑ІN(pin)∩...∩N(pim)+...
+(-1)k+1І N(p1)...N(pk)І
Dôk.aєN(pi1...pir)=>aa=>aєN(pi1)∩...∩N(pir)
aєi1)∩...∩N(pir)=>aєN(pi1)∩...∩aєN(pir)=>aaaєN}pi1...pir|
Dôk. vety φ(n)- ІN(p1)υ...υN(pk)І=n-∑ ІN(pi) І+∑ ІN(pi)∩
N(pj)+(-1)m+1∑ ІN(pi1)∩N(pi2)∩...∩N(pim) І+...=n-∑n/pi+∑n/pi1,pi2+∑n/pi1,pi2,pi3+∑n/pi1,...,pim)=n І 1-∑1/pi+∑1/pi1,pi2 –
∑1/pi1,pi2,pi3+ ..

І=Nn(-11/p1)(1-1/p2)...(1-1/pk)
І N(pi)∩N(pj) І= ІN(pi,pj)=n/pipj
ІN(p1)∩N(p2)∩N(p3) І=N Іpi1,pi2,pi3 І=n/pi1,pi2,pi3
ІN(pi1)∩...∩N(pim) І= ІN(pi1,...,pim) І=n/pi1,...,pim
(1-1/p1)(1-1/p2)...(1-1/pk)
13.Verejné šifrovanie systém
mєN, veľké k-dešifrovací kľúč
(x,m)=1;x(s,φ(m))=1 k=sφ(φ(m))-1(mod φ(m))
xs(mod m)=y k.s= sφ(φ(m))-1.s(mod φ(m))
k.s=sφ(φ(m)(mod φ(m)
yk≡xk.s(mod m) k.s≡s.1(mod φ(m))
xk≡xhφ(m)+1(mod m) k.s≡h.φ(m)+1
yk≡x(mod m)
14.Recionálne korene polinómových rovníc
V1ak j(x)=Qnxn+...+ab
Qn,Qn-1,...,RnєZ, a n≠0 a p/qєQ a(p,q)=1
J(p/q)=0 ;tak q/an ∩ p/Q0
V2.nech anxn+...+a0єZ(x)ς p/q Je zlomok v základnom tvare, ktorý je koreňom rovnice anxn+...+a0=0
Potom platí q/an a p/a0
Dôk. Qn(p/q)n+Qn-1(p/q)n-1+...+Q0=0 /qn
*Qnpn+an-1pn-1q1+an-2pn-2q2+...+a0qn=0

(p,q)=1 (p,qn)=1=>p/a0qn=>p/a0
*anpn+an-1pn-1q+an-2 pn-2q2+...+a0qn=0

q/anpn=>q/an.