Hallo,
Ik probeer al een tijdje de volgende dingen bewijzen, maar ik kom er niet helemaal uit, misschien kan iemand mij helpen?
Laat N,a in Z (gehele getallen) en a mod N en ook -a mod N in (Z/NZ)* (eenheidmodulo)
a) Voor welke restklassen a mod N geldt dat a mod N= -a mod N? (0nderscheid de gevallen N even en N oneven)
b) Laat zien dat φ(N) even is als N≥3.
Bij a dacht ik het volgende (maar ik denk wel dat het fout is): omdat a mod N in (Z/NZ)* zit is ggd(a,N)=1
a modN + amodN ≡ 2a modN ≡ 0 en dat betekent dus dat N even moet zijn.
Bij b weet ik niet echt wat ik moet doen, maar ik weet wel het volgende:
φ(N)= Π(p-1) p(vp(n)-1)=n Π(1-1/p) , waarbij het product over alle p|n gaat en p priem is.
Groetjes, Leslie
P.S. sorry dat sommige dingen niet goed getypt zijn maar ik kon de goede Z voor gehele getallen niet vinden en het teken voor in ook niet..
Laatste berichten
-
23:12
speciale rel. theorie 10
-
22:57
Straatklok loopt 5 minuten voor 11
-
22:57
wig 6
-
22:36
Gravity and gravitation 4
-
22:24
[scheikunde] vraag Chemie - wat is de oplossing? 10
-
19:47
Bruine vlekken op treinaanwijzerbord 10
-
19:44
Vogels in de stad zijn goede klussers 2
-
19:12
Rood laserlicht 3
-
17:30
Herleiden afmetingen vanaf een foto 21
-
16:34
[wiskunde] Prijs Product per KG; Alternatief Inzicht 3
-
13:57
do-re-mi-fa-so vliegtuigen 9
-
13:16
geen minkowski-ruimte toch? Doe ik dit nou fout? 17
-
13:12
[natuurkunde] kroon van koning op Syracuse 10
-
10:15
2013 – Augustus Vraag 3 3
-
24 apr
Vraag 2009 Juli Vraag 5 5
-
24 apr
positie 2
-
24 apr
Schroefdraad berekening 8
-
24 apr
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 9
-
23 apr
Weerfrustratie 9
-
23 apr
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 3
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
[wiskunde] bewijs met eenheidmodulo
Moderators: ArcherBarry, Fuzzwood
-
- Berichten: 8
Re: bewijs met eenheidmodulo
Bij vraag a:
Je hebt dat 2a≡0 mod N. Dit betekent dat N|2a. Maak nu onderscheid tussen N even en N oneven.
Vraag b: een getal is even als het minstens één priemfactor 2 heeft. Bekijk daarvoor enerzijds de oneven priemgetallen en anderzijds p=2, en wat die doen met φ(n).
Je hebt dat 2a≡0 mod N. Dit betekent dat N|2a. Maak nu onderscheid tussen N even en N oneven.
Vraag b: een getal is even als het minstens één priemfactor 2 heeft. Bekijk daarvoor enerzijds de oneven priemgetallen en anderzijds p=2, en wat die doen met φ(n).
-
- Berichten: 13
Re: bewijs met eenheidmodulo
Dank u wel, voor uw reactie. Ik snap het nog niet helemaal.
Dus bij a) 2 situaties:
Stel N is even dan N=2q en 2q|2a is mogelijk als q|a
Stel N is oneven dan N=2q+1 --> Kan niet dus N is even?
Ik weet niet waar ik nou precies heen ga..
En bij b) Wat bedoelt u met bekijk de oneven priemgetallen? want ik weet niet welke allemaal N delen, dus wat moet ik dan allemaal bekijken? Gewoon 3,5,7 en 11 ofzoiets? En moet ik hier dan allemaal het product van nemen? Ik snap niet hoe je terug naar N moet rekenen als je φ(N) hebt.
Dus nu heb ik: φ(N) = Π(p-1)pvp(n)-1=2x en p=2 geeft 1(2vp(n)-1)=2x maar hoe kom ik aan vp(n)?
Dus bij a) 2 situaties:
Stel N is even dan N=2q en 2q|2a is mogelijk als q|a
Stel N is oneven dan N=2q+1 --> Kan niet dus N is even?
Ik weet niet waar ik nou precies heen ga..
En bij b) Wat bedoelt u met bekijk de oneven priemgetallen? want ik weet niet welke allemaal N delen, dus wat moet ik dan allemaal bekijken? Gewoon 3,5,7 en 11 ofzoiets? En moet ik hier dan allemaal het product van nemen? Ik snap niet hoe je terug naar N moet rekenen als je φ(N) hebt.
Dus nu heb ik: φ(N) = Π(p-1)pvp(n)-1=2x en p=2 geeft 1(2vp(n)-1)=2x maar hoe kom ik aan vp(n)?
-
- Berichten: 10.179
Re: bewijs met eenheidmodulo
Voor b): stel dat n een oneven priemdeler heeft, dan ... Stel nu dat n geen oneven priemdeler heeft. Dan is n van de vorm 2^k voor een k. Dus phi(n) = ...
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 13
Re: bewijs met eenheidmodulo
Dank u wel voor uw reactie
Dan heb ik nu bij b): stel n heeft alleen een oneven priemdeler
Dan of alleen 1 als deler dan φ(n)=0
Of andere oneven delers dan φ(n)=Π(p-1)pvp((n)-1 en dit is even (want p-1 even dus elk onderdeel van het product even dus φ(n) is even.
Stel nu geen oneven priemdeler dan n is van de volgende vorm: n=2^k als ik dit invul krijg ik:
φ(2^k)= Π (2^k -1) 2k^2-k= Π2k^2-2k^2-k en dit is even want machten van 2 zijn altijd even.
Maar waarom sluit dit n=0,1,2 uit? Want volgens mijn conclusie is φ(n) altijd even..
En hoe moet ik verder met a?
Dan heb ik nu bij b): stel n heeft alleen een oneven priemdeler
Dan of alleen 1 als deler dan φ(n)=0
Of andere oneven delers dan φ(n)=Π(p-1)pvp((n)-1 en dit is even (want p-1 even dus elk onderdeel van het product even dus φ(n) is even.
Stel nu geen oneven priemdeler dan n is van de volgende vorm: n=2^k als ik dit invul krijg ik:
φ(2^k)= Π (2^k -1) 2k^2-k= Π2k^2-2k^2-k en dit is even want machten van 2 zijn altijd even.
Maar waarom sluit dit n=0,1,2 uit? Want volgens mijn conclusie is φ(n) altijd even..
En hoe moet ik verder met a?
-
- Berichten: 10.179
Re: bewijs met eenheidmodulo
Euhm,
Verder: snap je waarom n van de vorm 2^k is als n enkel even priemdelers heeft?
PS: vergeet niet dat 1 per definitie geen priemgetal is hè. En ook niet dat de Euler-phi-functie enkel gedefinieerd is voor strikt positieve getallen.
\(\phi(1) = 1\)
en \(\phi(2) = 1\)
. Verder heb je het iets verkeerd aangepakt nog. Ik zei niet "alleen oneven priemdelers", maar wel "een oneven priemdeler". Er kunnen dan ook even priemdelers zijn. Maar je aanpak kun bijna blijven dienen, zie je dat?Verder: snap je waarom n van de vorm 2^k is als n enkel even priemdelers heeft?
PS: vergeet niet dat 1 per definitie geen priemgetal is hè. En ook niet dat de Euler-phi-functie enkel gedefinieerd is voor strikt positieve getallen.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 13
Re: bewijs met eenheidmodulo
Waarom is φ(1)=1, want als ik het invul in de formule krijg ik 0 gezien de p-1?
Maar dan pas ik het dus op de volgende manier aan: het heeft een oneven priemdeler dus dat deel is even (door de p-1) de even priemdelers leveren ook een even getal op (want (1*(2^k-1)) is even dus het product van het totaal is even.
2^k heeft enkel even priemdelers, omdat de priemfactorisatie uniek is en het dus is 2*2*2*2... (k keer 2), toch?
Maar dan pas ik het dus op de volgende manier aan: het heeft een oneven priemdeler dus dat deel is even (door de p-1) de even priemdelers leveren ook een even getal op (want (1*(2^k-1)) is even dus het product van het totaal is even.
2^k heeft enkel even priemdelers, omdat de priemfactorisatie uniek is en het dus is 2*2*2*2... (k keer 2), toch?
-
- Berichten: 10.179
Re: bewijs met eenheidmodulo
Maar 1 is geen priemgetal! Dat werkt dus niet. Dat is gewoon per definitie. Jij wilt een (handige) formule gebruiken maar die is hier niet van toepassing.
De rest van je argumentatie is vrij warrig. Je maakt het moeilijker dan nodig. De eerste situatie: er is een oneven priemdeler p, dan is p-1 een deler van phi(n) (zie je dat?). Daar p oneven is, is p-1 even en dus... Kun je het afmaken?
Nu het andere: er zijn geen oneven priemdelers. Dus moet inderdaad 2 de enige priemdeler zijn en wegens (unieke) factorisatie is n van de vorm 2^k voor een k.
De rest van je argumentatie is vrij warrig. Je maakt het moeilijker dan nodig. De eerste situatie: er is een oneven priemdeler p, dan is p-1 een deler van phi(n) (zie je dat?). Daar p oneven is, is p-1 even en dus... Kun je het afmaken?
Nu het andere: er zijn geen oneven priemdelers. Dus moet inderdaad 2 de enige priemdeler zijn en wegens (unieke) factorisatie is n van de vorm 2^k voor een k.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 13
Re: bewijs met eenheidmodulo
Oke, ik snap het bewijs!
Alleen als 1 geen priem is hoe kun je 1 dan factoriseren in priemgetallen (gezien dat bij elk getal kan)? En hoe weet u dan dat φ(1)=1?
Kunt u mij ook verder helpen met a?
Alleen als 1 geen priem is hoe kun je 1 dan factoriseren in priemgetallen (gezien dat bij elk getal kan)? En hoe weet u dan dat φ(1)=1?
Kunt u mij ook verder helpen met a?
-
- Berichten: 10.179
Re: bewijs met eenheidmodulo
Grijp terug naar de definitie van de Euler-phi-functie: phi(n) is het aantal (natuurlijke) getallen k waarvoor geldt dat 0 ≤ k ≤ n en ggd(k, n) = 1. Als nu n=1, dan is het duidelijk er maar één zo'n getal k is (namelijk 1) en dus is phi(1) = 1.
Bij a) moet je eens een paar concrete N proberen. Neem eens N = 6, 7, 8, 9 en kijk dan voor welke a het geldt.
Bij a) moet je eens een paar concrete N proberen. Neem eens N = 6, 7, 8, 9 en kijk dan voor welke a het geldt.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 13
Re: bewijs met eenheidmodulo
Bij N=6 dan geldt het bij a=3 en a=6≡0
Bij N=7 dan geldt het bij a=7≡0
Bij N=8 dan geldt het bij a=4 en a=8≡0
Bij N=9 dan geldt het bij a=9≡0
Dus dan geldt het volgende bij de even getallen: restklassen N/2 en 0 en voor de oneven getallen alleen de restklasse 0?
Bij N=7 dan geldt het bij a=7≡0
Bij N=8 dan geldt het bij a=4 en a=8≡0
Bij N=9 dan geldt het bij a=9≡0
Dus dan geldt het volgende bij de even getallen: restklassen N/2 en 0 en voor de oneven getallen alleen de restklasse 0?
-
- Berichten: 10.179
Re: bewijs met eenheidmodulo
Wel, dat het voor 0 geldt is triviaal. Dat het bij N even geldt voor N/2 is ook niet supermoeilijk in te zien. De "uitdaging" is: waarom geldt het voor niets anders?
Ik heb je even wat concrete waarden laten nemen omdat je nu een idee hebt waar je naar toe wilt werken.
Ik heb je even wat concrete waarden laten nemen omdat je nu een idee hebt waar je naar toe wilt werken.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 13
Re: bewijs met eenheidmodulo
maar amodN=-amodN geeft: 2amodN=0 en dan is het toch gewoon logisch dat het niet voor de andere klassen geldt behalve a=0 of a=N/2 (als N is even). Er is verder geen a die aan die vergelijking voldoet toch?
-
- Berichten: 10.179
Re: bewijs met eenheidmodulo
Ja 
. Maar jij wou er hulp mee, dus...
. Maar jij wou er hulp mee, dus...Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
