Fin tallteorinøtt

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.

Fin tallteorinøtt

Innlegg Markus » 04/10-2018 22:05

Synes denne var fin. La $\tau(n)$ være antall divisorer til $n$, og $\sigma(n)$ være summen av disse divisorene. Vis da at for odde $n$ er $$\tau(n) \equiv \sigma(n) \pmod{2}$$
Markus offline
von Neumann
von Neumann
Innlegg: 531
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Fin tallteorinøtt

Innlegg Gustav » 05/10-2018 06:48

$n$ kan skrives på formen $\prod_i p_i^{q_i}$, der $p_i$ er odde primfaktorer. En divisor vil da være på formen $d_r=\prod_i p_i^{r_i}$ der $0\le r_i\le q_i$. Siden $p_i$ er odde vil $d_r\equiv 1\pmod 2$ så hver divisor bidrar med $1$ i summen av alle divisorene modulo 2, og da er det klart at $\tau(n)=\sigma(n)\pmod 2$.
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4160
Registrert: 12/12-2008 12:44

Re: Fin tallteorinøtt

Innlegg Markus » 05/10-2018 20:27

Gustav skrev:$n$ kan skrives på formen $\prod_i p_i^{q_i}$, der $p_i$ er odde primfaktorer. En divisor vil da være på formen $d_r=\prod_i p_i^{r_i}$ der $0\le r_i\le q_i$. Siden $p_i$ er odde vil $d_r\equiv 1\pmod 2$ så hver divisor bidrar med $1$ i summen av alle divisorene modulo 2, og da er det klart at $\tau(n)=\sigma(n)\pmod 2$.

Elegant løsning!

Alternativt, men litt lengre. For alle primtall $p > 2$ er det åpenbart at $p \equiv 1 \pmod{2} \implies p^j \equiv 1 \pmod{2} \enspace \forall j \in \mathbb{N}$. Eksplisitt, hvis $n=p_1^{r_1}p_2^{r_2}\cdots p_t^{r_t}$ er $$\begin{alignat*}{2} \sigma(n)&=\left(1+p_1+p_1^2+\dots p_1^{r_1} \right)\left(1+p_2+p_2^2 + \dots + p_2^{r_2}\right) \cdots \left(1+p_t+p_t^2+\dots+p_t^{r_t} \right) \\ &\equiv \left (\underbrace{1+1+\dots+1}_{r_1+1 \text{ ganger}} \right)\left (\underbrace{1+1+\dots+1}_{r_2+1 \text{ ganger}} \right) \cdots \left( \underbrace{1+1+\dots+1}_{r_t+1 \text{ ganger}} \right) \pmod{2} \\ &= (r_1+1)(r_2+1)\cdots (r_t+1) \\ &= \tau(n) \end{alignat*}$$
Markus offline
von Neumann
von Neumann
Innlegg: 531
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Fin tallteorinøtt

Innlegg Gustav » 13/10-2018 19:18

Når jeg tenker meg om er jo egentlig det vi skal vise helt åpenbart, og vi behøver strengt tatt ikke introdusere noen notasjon i det hele tatt. Siden $n$ er odde vil jo alle divisorer være ekvivalent med 1 modulo 2, og da vil selvsagt summen av divisorene være ekvivalent med antall divisorer.
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4160
Registrert: 12/12-2008 12:44

Re: Fin tallteorinøtt

Innlegg Markus » 13/10-2018 20:30

Gustav skrev:Når jeg tenker meg om er jo egentlig det vi skal vise helt åpenbart, og vi behøver strengt tatt ikke introdusere noen notasjon i det hele tatt. Siden $n$ er odde vil jo alle divisorer være ekvivalent med 1 modulo 2, og da vil selvsagt summen av divisorene være ekvivalent med antall divisorer.

Huff, det er helt sant. Hadde helt oversett det.
Over til noe annet, har du en oppfølger?
Markus offline
von Neumann
von Neumann
Innlegg: 531
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Fin tallteorinøtt

Innlegg Aleks855 » 13/10-2018 22:02

La $a, b \in \mathbb N$ slik at $ab+1 | a^2 + b^2$. Vis at $\frac{a^2 + b^2}{ab+1}$ er kvadratet av et heltall.
Bilde
Aleks855 offline
Rasch
Rasch
Innlegg: 5476
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Fin tallteorinøtt

Innlegg stensrud » 14/10-2018 16:24

Aleks855 skrev:La $a, b \in \mathbb N$ slik at $ab+1 | a^2 + b^2$. Vis at $\frac{a^2 + b^2}{ab+1}$ er kvadratet av et heltall.

:(
stensrud offline
Descartes
Descartes
Innlegg: 426
Registrert: 08/11-2014 21:13
Bosted: Cambridge

Re: Fin tallteorinøtt

Innlegg Markus » 14/10-2018 17:00

Aleks855 skrev:La $a, b \in \mathbb N$ slik at $ab+1 | a^2 + b^2$. Vis at $\frac{a^2 + b^2}{ab+1}$ er kvadratet av et heltall.

Hvis noen har et annet bevis enn det som er "standard" (det med Vieta Root jumping) så må dere gjerne skrive det :D
Markus offline
von Neumann
von Neumann
Innlegg: 531
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Fin tallteorinøtt

Innlegg Aleks855 » 14/10-2018 18:51

stensrud skrev:
Aleks855 skrev:La $a, b \in \mathbb N$ slik at $ab+1 | a^2 + b^2$. Vis at $\frac{a^2 + b^2}{ab+1}$ er kvadratet av et heltall.

:(


Samme her. Tror denne oppgaven er noen dusin hakk over mitt tallteori-nivå, men den virket så enkel ved første øyekast.

IMO 1988, oppgave 6, forresten.
Bilde
Aleks855 offline
Rasch
Rasch
Innlegg: 5476
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Fin tallteorinøtt

Innlegg Gustav » 14/10-2018 22:22

Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4160
Registrert: 12/12-2008 12:44

Re: Fin tallteorinøtt

Innlegg Aleks855 » 14/10-2018 22:29

Haha, jeg har sett den videoen for lenge siden, men husket ikke at det var denne oppgaven.

Jeg fant bare oppgaven i denne pdf'en (https://www.math.muni.cz/~bulik/vyuka/pen-20070711.pdf). Som dere ser så har jeg ikke kommet langt før jeg fant denne.
Bilde
Aleks855 offline
Rasch
Rasch
Innlegg: 5476
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Fin tallteorinøtt

Innlegg Markus » 14/10-2018 22:58

Morsom video det der!

Denne er sikkert kjent for mange, men en annen fin tallteorinøtt, som ikke er sånn rett fram uten videre (men dog ganske mye lettere enn de problemene i den PDFen) er å vise følgende ekvivalens
$x^2+1\equiv 0 \pmod{p} \Longleftrightarrow p=4k+1$, altså $p$ er primtall på formen $4k+1$.
Markus offline
von Neumann
von Neumann
Innlegg: 531
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Fin tallteorinøtt

Innlegg Aleks855 » 15/10-2018 08:27

stensrud skrev:
Aleks855 skrev:La $a, b \in \mathbb N$ slik at $ab+1 | a^2 + b^2$. Vis at $\frac{a^2 + b^2}{ab+1}$ er kvadratet av et heltall.

:(


Gjorde du et forsøk og fant ut at oppgaven var vanskelig, eller var det bare en oppgitthet over at jeg posta en notorisk vanskelig oppgave? :D
Bilde
Aleks855 offline
Rasch
Rasch
Innlegg: 5476
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 16 gjester