Osztas és oszthatósagok

Osztás és oszthatóságok

Maradékos osztás definíciója: az a művelet, amely két egész számmal dolgozik. N=egész szám m> 0 egész. Meghatározza a q és r egészt.

n = m × q + r   0 < = r < m

n =osztandó

m =osztó (amivel osztunk)

q =hányados = n div m

r =maradék = n mod m

Példa :    n=19 m=3 à 0<=1<3

19 div 3=6

19 mod 3=1

Elvárások: Létezés (elvégezhetőség)

Egyértelműség

Tétel: Legyen m>0 egész szám. Minden egészre létezik olyan q vagy r egész szám n=m×q+r

A q és az r egyértelműen meghatározott.

Bizonyítás: 1. Létezés

Legyen m>0 egész

n tetszőleges egész

Létezik olyan q egész, hogy az m×q<=n<m(q+1) à mq+m

0<=n-m×q<m

Legyen r=n-m×q

Látható: 0<=r<m mivel r=n-m×q à n=m×q+r

2. Egyértelműség |n=m×q₁+r₁ (0<=r₁<m)

|n=m×q₂+r₂ (0<=r₂<m)

Feltehető, hogy r₁=>r₂ (-) 0=m(q₁-q₂)+(r₁-r₂)

0<=r₁-r₂<m r₁-r₂=m(q₂-q₁)

Lehet-e a q₂-q₁<0? Nem lehet!

Lehet-e a q₂-q₁>0 r₁-r₂=m(q₂-q₁)>m Nem lehet!

q₂-q₁=0à q₁=q₂         r₁=r₂

Következményei: - Osztó: 2

Maradék: 0, 1

Tetszőleges egész szám: n

n=2k+0=2k : - páros számok

n=2k+1 : - páratlan számok

Kérdés: egy szám négyzete néggyel osztva milyen maradékot ad?

n=2k à n²=4k²+0 n² mod2=0

n=2k+1à n²=4k²+4k+1=4(k²+k)+1 n² mod 4=1

Tulajdonságai:

Definíció: n egész osztója m egésznek ha létezik olyan q egész szám, hogy az n×q=m

Jelölés: n (osztó)/m (többszörös)

Lineáris kombináció: az m és n egészek α×m+β×n összegét értjük.

Példa: n=13 ×21+ ×13 ^{(lineáris kombináció)}

m=21 (együtthatók)

Tétel:

Ha m/n₁ és m/n₂ à m/α×m₁+ß×m₂

m/n₁ à m/n₁×n₂

Ha m₁/n₁ és m₂/n₂ à m₁×m₂/n₁×n₂

+-1/n   n/0

Bizonyítás: Legyen m/n₁ à n₁=m×q₁ és m/n₂à n₂= m×q₂

α×n₁+ß×n₂=α×m×q₁+ ß×m×q₂

(α×q₁+ß×q₂)×m=m×q

Tfh m/n₁=? N₁=m×q

N₁×n₂=m(q×n₂)à m/n₁×n₂

m₁|n₁à n₁=m₁×q₁

m₂|n₂à n₂=m₂×q₂

}× ^szorzás n₁×n₂=m₁×q₁ m₂×q₂=(m₁×m₂)×(q₁×q₂)=m₁×m₂×q

m₁×m₂|n₁×n₂

Definíció: az 1 osztóit egységeknek nevezzük.

Tétel: m|m (reflexive tulajdonság)

(tranzitív tulajdonság) Ha m|n és n|k à m|k

Tfh m|n és n|k

↓ ↓

n=m×q k=n×t

k=m(q×t)à m|k

Ha m|n és n|m akkor n=+-m

d/n à-d/n

N=d×q à n=(-d)×(-q) à-d/n

n=(-d)×q à n=d×(-q) à d/n

Ha ismerjük egy szám pozitív osztóit akkor ismerjük az összes osztót

n>0

d/n à d/-n

Pozitív szám pozitív osztója nem lehet nagyobb az adott számnál. n>0 osztóit: halmazban kell kezdeni. -d/n n=d×q ekkor nemcsak d, hanem q adott à célszerű osztópárokról beszélni.

Ha (d, q) osztópár akkor lehet-e d és q >√n d, q>n Nem igaz.

D és q közül legalább az egyik kisebb vagy egyenlő mint [√n] à elegendő n halmazt vizsgálni.

Osztópárok meghatározása

Algoritmus S=(1,40), (2,20), (4,10), (5,8)

Indukció és redukció fogalma!

n

1. Jelölés: ∑ (szigma) ejtsd: szumma ∑ a×i=a₁+a₂+a₃...a_n

i=1