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:
Noen primtallsnøtter
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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$.
\[ 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$.
$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$.Markus skrev: 3) Hvor mange primtall er det i følgen $2018!+2,2018!+3,\dots+,2018!+2017,2018!+2018$?
Pene og effektive bevis Gustav og Stensrud. Gjorde de likt selv.
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$.
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$.stensrud skrev:Oppfølger:
4) Vis at $2^n-1$ ikke er delelig med $n$ for $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.
5) Her må det vel være en feil i formuleringenMarkus 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$.
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 heheGustav skrev:5) Her må det vel være en feil i formuleringenMarkus 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$.
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.
. Har endret det nå!