Noen primtallsnøtter

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

1) Anta at $a^n-1$ er et primtall og at $n \geq 2$, vis at det er nødvendig at $a=2$.
2) Vis at $2^{jk}-1$ ikke kan være et primtall dersom $j \geq 2$, $k \geq 2$
3) Hvor mange primtall er det i følgen $2018!+2,2018!+3,\dots+,2018!+2017,2018!+2018$?

Hint:
[+] Skjult tekst
1) Kan $a^n-1$ faktoriseres på en måte?
2) Bruk samme faktoriseringsmetode som i a)
3) Igjen, faktoriser.
stensrud
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Sted: Cambridge

Det var få meldte seg, så jeg tar (1): Observer at
\[ a^n-1=(a-1)\sum_{i=0}^{n-1}a^i. \]
Det er klart at $a$ må være lik $2$ for at det over skal være et primtall.

Oppfølger:
4) Vis at $2^n-1$ ikke er delelig med $n$ for $n>1$.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Markus skrev: 3) Hvor mange primtall er det i følgen $2018!+2,2018!+3,\dots+,2018!+2017,2018!+2018$?
$2018!+n= n(\frac{2018!}{n}+1)$ for alle heltall $2\le n\le 2018$, følgelig er samtlige tall i følgen sammensatte da begge faktorer er større enn $1$.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Markus skrev: 2) Vis at $2^{jk}-1$ ikke kan være et primtall dersom $j \geq 2$, $k \geq 2$
$2^{jk}-1=(2^j)^k-1 = (2^j-1)\sum_{i=0}^{k-1} 2^{ij}$, som er sammensatt for $j,k \ge 2$ da begge faktorer er heltall større enn $1$.
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

Pene og effektive bevis Gustav og Stensrud. Gjorde de likt selv.
stensrud skrev:Oppfølger:
4) Vis at $2^n-1$ ikke er delelig med $n$ for $n>1$.
Det er ganske klart at vi kun trenger å se på odde $n$ siden $2^n-1$ alltid er odde, og således kan aldri et partall dele $2^n-1$.

Anta, i jakt på selvmotsigelse, at $\exists n: n \mid (2^n-1)$. Se på den minste primfaktoren, $p$, til $n$. Det er klart at $p \mid n \implies p \mid (2^n-1) \Longleftrightarrow 2^n \equiv 1 \pmod{p}$. Siden at $p$ er det minste primtallet som deler $n$, og således den minste divisoren til $n$, må det være slik at $p-1$ og $n$ ikke deler noen felles faktorer, altså $\gcd(p-1,n)=1$. Siden at det for alle gcd-er eksisterer $x,y \in \mathbb{Z}$ slik at $\gcd(a,b)$ kan skrives som en lineær kombinasjon på formen $ax+by=\gcd(a,b)$, har vi at $(p-1)x+ny = 1$. Anta nå wlog at $p>2$, da har vi at $\gcd(2,p)=1$ for alle primtall $p$. Derfor kan vi ta i bruk Fermats lille teorem som gir oss at $2^{p-1} \equiv 1 \pmod{p} \implies \left(2^{p-1}\right)^x \equiv 2^{(p-1)x} \equiv 1 \pmod{p}$. Antakelsen var at $2^n \equiv 1 \pmod{p} \implies \left(2^n\right)^y \equiv 2^{ny} \equiv 1 \pmod{p}$. Dette sammen gir oss endelig at $2^{(p-1)x} \cdot 2^{ny} \equiv 1 \pmod{p}$ men $2^{(p-1)x} \cdot 2^{ny} = 2^{(p-1)x + ny} = 2^1 \not \equiv 1 \pmod{p}$. En selvmotsigelse som fullfører beviset.

Oppfølgere:
5) La $\{p_1,p_2,\dots,p_t\}$ være en endelig mengde primtall slik at $p_1 \neq p_2 \neq \dots \neq p_t$. Vis at $\sum_{i=1}^t \frac{1}{p_i}$ aldri er et heltall.
6) La $\{a_1,a_2,\dots,a_n\}$ være en komplett mengde av rester modulo $n$ og $\gcd(a,n)=1$. Vis at da er $\{aa_1,aa_2,\dots,aa_n\}$ også er komplett mengde av rester modulo $n$.
Sist redigert av Markus den 18/10-2018 01:20, redigert 1 gang totalt.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Markus skrev: Oppfølgere:
5) La $\{p_1,p_2,\dots,p_t\}$ være en endelig mengde primtall slik at $p_1 \neq p_2 \neq \dots \neq p_t$. Vis at $\sum_{i=1}^t p_i$ aldri er et heltall.
6) La $\{a_1,a_2,\dots,a_n\}$ være en komplett mengde av rester modulo $n$ og $\gcd(a,n)=1$. Vis at da er $\{aa_1,aa_2,\dots,aa_n\}$ også er komplett mengde av rester modulo $n$.
5) Her må det vel være en feil i formuleringen

6) Bevis ved motsigelse: Anta at det fins $i\neq j$ slik at $aa_i\equiv aa_j\pmod n$. Siden $\gcd(a,n)=1$ fins en multiplikativ invers til $a$, så multiplikasjon fra venstre med $a^{-1}$ gir $a^{-1}aa_i\equiv a^{-1}aa_j\Rightarrow a_i\equiv a_j$, som er en motsigelse siden $\{a_1,a_2,...,a_n\}$ er en komplett mengde av rester.
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

Gustav skrev:
Markus skrev: Oppfølgere:
5) La $\{p_1,p_2,\dots,p_t\}$ være en endelig mengde primtall slik at $p_1 \neq p_2 \neq \dots \neq p_t$. Vis at $\sum_{i=1}^t p_i$ aldri er et heltall.
6) La $\{a_1,a_2,\dots,a_n\}$ være en komplett mengde av rester modulo $n$ og $\gcd(a,n)=1$. Vis at da er $\{aa_1,aa_2,\dots,aa_n\}$ også er komplett mengde av rester modulo $n$.
5) Her må det vel være en feil i formuleringen

6) Bevis ved motsigelse: Anta at det fins $i\neq j$ slik at $aa_i\equiv aa_j\pmod n$. Siden $\gcd(a,n)=1$ fins en multiplikativ invers til $a$, så multiplikasjon fra venstre med $a^{-1}$ gir $a^{-1}aa_i\equiv a^{-1}aa_j\Rightarrow a_i\equiv a_j$, som er en motsigelse siden $\{a_1,a_2,...,a_n\}$ er en komplett mengde av rester.
Yes, flott! Ja, på 5 så skulle det selvfølgelig være en brøk hehe :oops: . Har endret det nå!
Svar