Springen naar inhoud

bewijs met eenheidmodulo



  • Log in om te kunnen reageren

#1

Leslie Zwerwer

    Leslie Zwerwer


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 26 april 2013 - 19:07

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..

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

barto

    barto


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 26 april 2013 - 20:26

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).

#3

Leslie Zwerwer

    Leslie Zwerwer


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 26 april 2013 - 22:27

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)?

Veranderd door Leslie Zwerwer, 26 april 2013 - 22:31


#4

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 27 april 2013 - 00:14

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.

#5

Leslie Zwerwer

    Leslie Zwerwer


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 27 april 2013 - 08:32

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?

Veranderd door Leslie Zwerwer, 27 april 2013 - 08:33


#6

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 27 april 2013 - 09:02

Euhm, LaTeX en LaTeX . 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.

#7

Leslie Zwerwer

    Leslie Zwerwer


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 27 april 2013 - 10:21

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?

#8

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 27 april 2013 - 10:30

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.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#9

Leslie Zwerwer

    Leslie Zwerwer


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 27 april 2013 - 13:41

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?

#10

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 27 april 2013 - 14:29

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.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#11

Leslie Zwerwer

    Leslie Zwerwer


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 27 april 2013 - 21:56

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?

#12

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 27 april 2013 - 22:12

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.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#13

Leslie Zwerwer

    Leslie Zwerwer


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 28 april 2013 - 11:55

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?

#14

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 28 april 2013 - 12:52

Ja :P. Maar jij wou er hulp mee, dus...
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#15

Leslie Zwerwer

    Leslie Zwerwer


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 28 april 2013 - 18:39

Oo hahah, heel erg bedankt!






Also tagged with one or more of these keywords: wiskunde

0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures