Matematik

Kongruenser - primtal

20. september 2016 af 9003n (Slettet) - Niveau: Universitet/Videregående

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å 4p₁p₂ ... p_n-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 p² 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

Brugbart svar (0)

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 p² ≡ 1 mod 4

Svar #2
20. september 2016 af 9003n (Slettet)

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 p²?

og ved du, hvilke(n) sætning(er) man bruger, for at komme frem til dette?

Brugbart svar (0)

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 (Slettet)

aha.. hvordan kan jeg så vise at der uendeligt mange primtal kongruente til 3 mod 4, vha euklids bevis?

Svar #5
20. september 2016 af 9003n (Slettet)

ingen der kan hjælpe?

Brugbart svar (0)

Svar #6
21. september 2016 af VandalS

Til andet delspørgsmål:

Antag, at der en endelig mængde $\{ p_1, p_2, ..., p_n\}$ af primtal der er kongruente til 3 modulo 4. Betragt tallet $p=-1+4 \prod_{i=1}^n p_i$ . Da alle $p_m, m\in \{ 1,2, ..n\}$ dividerer $4\prod_{i=1}^np_i$ kan ingen af dem dividere .

Vi har desuden at

$p \mod 4 = 4\prod_{i=1}^n p_i -1 \mod 4 \equiv -1 \mod 4 \equiv 3 \mod 4$ ,

så per første delopgave har en primfaktor, der er kongruent med 3 modulo 4. Da ingen af primtallene $\{p_1, p_2, ... , p_n\}$ 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 (Slettet)

Okay, men det du skriver efter "p mod 4 = 4, hvor der kommer et tegn mwd et n ovenpå , hvad erdet det betyder, og kan det ikke betegnes på en anden måde?

Brugbart svar (0)

Svar #8
21. september 2016 af peter lind

Du har læst forkert. Der står at (4*p1*p₂*...p_n-1) ≡-1 mod 4 og dermed (4*p₁*p₂*...p_n-1) ≡3 mod 4

Brugbart svar (0)

Svar #9
21. september 2016 af VandalS

#7 Tegnet er et uppercase $\pi$ og bruges til produkter på samme måde som $\sum$ bruges til summer; f.eks. er

$\prod_{i=1}^3 p_i = p_1 \cdot p_2 \cdot p_3$ . Jeg bruger det bare til at gøre notationen mere kortfattet.

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.