Matematik
Kongruenser - primtal
Hej
Jeg sidder med en opgave som lyder således:
Vis, at et helt tal* der er kongruent til 3 modulo 4, har en primfaktor, der er kongruent til 3 modulo 4.
Vis, at der er uendeligt mange primtal, der er kongruente til 3 modulo 4. (følg euklids bevis for, at der er uendelig mange primtal, men kig på 4p1p2 ... pn-1)
* ("et helt tal" rettes til "et naturligt tal")
Jeg har kigget på det, og fået af vide (via et andet tråd) at jeg skal finde ud af, hvilke værdier p mod 4 kan antage, og hvilke værdier p2 mod 4 antage, til at starte med. Men jeg forstår ikke helt, hvordan dette skal gøres? og hvordan jeg efterfølgende kan bruge det til at komme videre i næste opg.
tak på forhånd
Svar #1
20. september 2016 af peter lind
restklassen 3 mod 4 er sin egen inverse. Hvis a ≡ 3 mod 4 er a invertibel og kan altså kun bestå af produkter af tal der er invertible og a kan ikke kun have faktorer der kun er kongruent til 1 modulo 4. Der må så gælde for p ≠2 at p2 ≡ 1 mod 4
Svar #2
20. september 2016 af 9003n
Okay, har lige nogle ting som jeg stadig ikke helt har styr på.
Hvad menes der med, at 3 mod 4 er "sin egen inverse"?, og hvorfor er det egentlig man skal finde p2?
og ved du, hvilke(n) sætning(er) man bruger, for at komme frem til dette?
Svar #3
20. september 2016 af peter lind
Det betyder at hvis du ganger tallet med sig selv får du et tal der ligger i restklassen 1 modulo 4
Svar #4
20. september 2016 af 9003n
aha.. hvordan kan jeg så vise at der uendeligt mange primtal kongruente til 3 mod 4, vha euklids bevis?
Svar #6
21. september 2016 af VandalS
Til andet delspørgsmål:
Antag, at der en endelig mængde af primtal der er kongruente til 3 modulo 4. Betragt tallet . Da alle dividerer kan ingen af dem dividere .
Vi har desuden at
,
så per første delopgave har en primfaktor, der er kongruent med 3 modulo 4. Da ingen af primtallene er faktorer i må det betyde at selv er et primtal der er kongruent til 3 modulo 4, hvilket er i modstrid med at vi havde listet alle sådanne primtal. Vi har dermed vist at der findes uendeligt mange primtal, der er kongruente til 3 modulo 4.
Svar #7
21. september 2016 af 9003n
Svar #8
21. september 2016 af peter lind
Du har læst forkert. Der står at (4*p1*p2*...pn-1) ≡-1 mod 4 og dermed (4*p1*p2*...pn-1) ≡3 mod 4
Skriv et svar til: Kongruenser - primtal
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.