[Wiskunde]Deelbaarheid bewijzen

[IvdSangen]

Hoe kan ik bewijzen dat 17 een deler is van 10⁸+1?

Edit: Sorry, deze opgave had ik al opgelost.

De vraag die ik wilde stellen was:

Hoe kan ik bewijzen dat 2¹⁰⁰⁰+5 niet priem is?

Zeggen dat het deelbaar is door 3

sdfg3g34gdeg schreef op 13-01-2005 @ 20:51 :
Zeggen dat het deelbaar is door 3

Dat geldt overigens voor elke evenmacht van 2+5.

[Young Grow Old]

De enige manier om te bewijzen dat een getal niet priem is, is inderdaad door de ontbinding, of in ieder geval een deler te vinden. 3 is inderdaad een deler, zoals sdfg3g34gdeg opmerkte. Dit is niet moeilijk in te zien dmv modulo-rekenen:
2*2 =4 eq 1 mod 3, dus 2*2^500 eq 1^500=1 mod 3.
1+5=6 eq 0 mod 3 en dus deelbaar door 3.

[IvdSangen]

Bedankt, duidelijk.

Young Grow Old schreef op 13-01-2005 @ 21:27 :
De enige manier om te bewijzen dat een getal niet priem is, is inderdaad door de ontbinding, of in ieder geval een deler te vinden. 3 is inderdaad een deler, zoals sdfg3g34gdeg opmerkte. Dit is niet moeilijk in te zien dmv modulo-rekenen:
2*2 =4 eq 1 mod 3, dus 2*2^500 eq 1^500=1 mod 3.
1+5=6 eq 0 mod 3 en dus deelbaar door 3.

zou je eventueel het modulo rekenen even uit kunnen leggen, want ik heb het nooit geleerd, maar in de informatica vakken van mijn studie kom ik het soms tegen (al dan niet significant), maar ik wil gewoon weten hoe het werkt
en dan meer dan alleen "rest na deling"

[Young Grow Old]

FlorisvdB schreef op 14-01-2005 @ 04:56 :
zou je eventueel het modulo rekenen even uit kunnen leggen, want ik heb het nooit geleerd, maar in de informatica vakken van mijn studie kom ik het soms tegen (al dan niet significant), maar ik wil gewoon weten hoe het werkt
en dan meer dan alleen "rest na deling"

De getallen zijn inderdaad gebaseerd op 'rest na deling'. Een getal x is equivalent met n mod p als x-n deelbaar is door p. Je kunt het getal voor zekere k dus schrijven als x=k*p+n.
Op zich is hier natuurlijk weinig bijzonders aan, maar het bijzondere is dat zo een verzameling restklassen modulo p {0,1,2,......,p-1} een eindige ring vormt (en zelfs een lichaam als p priemgetal is) (Ik hoop dat je de eisen kent voor een ring/lichaam) met de bewerkingen optellen en vermenigvuldigen: Je kunt dus de restklassen optellen en vermenigvuldigen, precies zoals je dat in de ring van de gehele getallen zou doen.
Vb. neem p=3.
11 eq 2 mod 3. (11=3*3+2)
13 eq 1 mod 3. (13=4*3+1).
11*13 zou dan 2*1 eq 2 mod 3 op moeten leveren en 11+13 zou 2+1=3=1*3+0 eq 0 mod 3 op moeten leveren.
11*13=143=47*3+2
11+13=24=8*3+0.
Je ziet dus dat het klopt.
Het is niet moeilijk aan te tonen dat het inderdaad altijd klopt:
schrijf een getal x uniek als k*p+n met n<p
en een ander getal y als q*p+m met m<p.
dan: x*y=k*q*p²+n*q*p+m*k*p+n*m.
Zoals je ziet zijn de eerste drie termen allen deelbaar door p, dus leveren deze 0 mod p op. (het getal is schrijfbaar als (k*q*p+n*q+m*k)*p+n*m. Gevolg: x*y eq n*m mod p.
Hetzelfde voor de optelling:
schrijf een getal x uniek als k*p+n met n<p
en een ander getal y als q*p+m met m<p.
x+y=k*p+q*p+n+m=(k*q)*p+(n+m).

bedankt
ik ken alleen niet de eisen voor een ring/lichaam...

[mathfreak]

FlorisvdB schreef op 15-01-2005 @ 20:42 :
bedankt
ik ken alleen niet de eisen voor een ring/lichaam...

Ik wel . Een ring is een getalverzameling met daarin een optelling, een aftrekking en een vermenigvuldiging gedefinieerd, waarbij ieder element a een tegengestelde -a heeft. Een lichaam is een ring, waarin ook een deling (behalve door nul) gedefinieerd is, en waarbij ieder element a (ongelijk aan nul) een omgekeerde a' heeft, met a*a'=1.

[Young Grow Old]

mathfreak schreef op 15-01-2005 @ 20:51 :
Ik wel . Een ring is een getalverzameling met daarin een optelling, een aftrekking en een vermenigvuldiging gedefinieerd, waarbij ieder element a een tegengestelde -a heeft. Een lichaam is een ring, waarin ook een deling (behalve door nul) gedefinieerd is, en waarbij ieder element a (ongelijk aan nul) een omgekeerde a' heeft, met a*a'=1.

Er hoeft niet zo zeer een aftrekking of een deling te zijn, als wel een tegengestelde respectievelijk inverse element waarmee optelling/vermenigvuldiging uitgevoerd wordt. Delen modulo p is moeilijk voor te stellen.
Voor de volledigheid dan maar de 9 eisen voor een lichaam:
Een lichaam is een verzameling V met twee bewerkingen + en *, die voldoen aan:
1. + is associatief; (x+y)+z=x+(y+z) voor alle x,y,z in V
2. er is een 0-element, zodat 0+x=x+0=x voor alle x in V
3. voor elke x in V is er een tegensgestelde (-x) in V, zodat x+(-x)=0.
4. + is commutatief: x+y=y+x voor alle x,y in V
5. * is associatief
6. er is een 1 in V, zodat 1*x=x*1=1 voor alle x in V
7. voor elke x ongelijk 0 in V is er een inverse x^-1 in V, zodat x*x^-1=1
8. * is commutatief
9. * is distributief over +: x*(y+z)=x*y+x*z en (x+y)*z=x*z+y*z voor alle x,y,z in V

Een groep voldoet aan 1,2,3
een abelse groep voldoet aan 1,2,3,4
een ring voldoet aan 1,2,3,4,5,6,9
een commutatieve ring voldoet aan 1,2,3,4,5,6,8,9.
In het geval van modulorekenen geldt dat je een commutatieve ring modulo p hebt als p geen priem en een lichaam als p wel priem.