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