Tallteori

[Gustav]

1) Finn alle tripler $(p,x,y)$ slik at $p^x=y^4+4$ hvor $p$ er primtall, og $x$ og $y$ er naturlige tall.

2) La $p$ være et primtall større enn $3$. Finn alle par $(x,y)$ av heltall som tilfredsstiller $x^2+3xy+2p(x+y)+p^2=0$.

[Gjest]

Hei, jeg er håpløs på slike oppgaver. Finnes det en bestemt fremgangsmåte?

[tex]p^x=y^4+4\Leftrightarrow p^x=(y^2-2y+2)(y^2+2y+2)[/tex]

kommer ikke egentlig lenger.. utrykkene i parentesen må jo tydeligvis være større en null. men jeg er lost.. kommer ikke på noe mer .

[stensrud]

Hei, jeg er håpløs på slike oppgaver. Finnes det en bestemt fremgangsmåte?

[tex]p^x=y^4+4\Leftrightarrow p^x=(y^2-2y+2)(y^2+2y+2)[/tex]

kommer ikke egentlig lenger.. utrykkene i parentesen må jo tydeligvis være større en null. men jeg er lost.. kommer ikke på noe mer .

Du har jo kommet veldig langt på vei bare ved å finne faktoriseringen; det gjenstår kun et par vurderinger før du er i mål.

Merk at forskjellen mellom faktorene på høyre side er lik $4y$, og derfor må deres største felles divisor også dele nettopp $4y$. Men ettersom $p$ er et odde primtall må også $y$ være odde, og da er ingen av $(y^2-2y+2)$ eller $(y^2+2y+2)$ odde heller, så faktorenes største felles divisor er odde (og divisor i $y$). Som sagt er $y$ odde, og dermed innbyrdes primisk med $2$, slik at ingen av faktorene er delelig med $y$ heller; de gir rest $2$ ved divisjon på $2$. Tilsammen får vi at $\gcd{(y^2-2y+2),(y^2+2y+2)}=1$

Det følger at enten $(y^2-2y+2)$ eller $(y^2+2y+2)$ er lik $1$ (de er alltid positive). Dette gir henholdsvis $y=1$ og $y=-1$, hvor den siste løsningen forkastes siden $y\in\mathbb{N}$. Eneste løsning er $(p,x,y)=(5,1,1)$.

Er ikke den mest erfarne her når det kommer til dette, men jeg vil si at det som regel ikke finnes en bestemt fremgangsmåte for disse oppgavene, og at det er det som gjør de så artige (vanskelige) å løse. Likevel finnes det en del metoder som går igjen, som for eksempel å faktorisere, finne største felles divisor, si noe om delelighet osv, så er trikset da å vite når man skal benytte seg av de forskjellige.

[Gjest]

hva er trisket på den andre? Ser ikke ut som lar vær å faktorisere.

[Gjest]

Hei, jeg er håpløs på slike oppgaver. Finnes det en bestemt fremgangsmåte?

[tex]p^x=y^4+4\Leftrightarrow p^x=(y^2-2y+2)(y^2+2y+2)[/tex]

kommer ikke egentlig lenger.. utrykkene i parentesen må jo tydeligvis være større en null. men jeg er lost.. kommer ikke på noe mer .

Du har jo kommet veldig langt på vei bare ved å finne faktoriseringen; det gjenstår kun et par vurderinger før du er i mål.

Merk at forskjellen mellom faktorene på høyre side er lik $4y$, og derfor må deres største felles divisor også dele nettopp $4y$. Men ettersom $p$ er et odde primtall må også $y$ være odde, og da er ingen av $(y^2-2y+2)$ eller $(y^2+2y+2)$ odde heller, så faktorenes største felles divisor er odde (og divisor i $y$). Som sagt er $y$ odde, og dermed innbyrdes primisk med $2$, slik at ingen av faktorene er delelig med $y$ heller; de gir rest $2$ ved divisjon på $2$. Tilsammen får vi at $\gcd{(y^2-2y+2),(y^2+2y+2)}=1$

Det følger at enten $(y^2-2y+2)$ eller $(y^2+2y+2)$ er lik $1$ (de er alltid positive). Dette gir henholdsvis $y=1$ og $y=-1$, hvor den siste løsningen forkastes siden $y\in\mathbb{N}$. Eneste løsning er $(p,x,y)=(5,1,1)$.

Er ikke den mest erfarne her når det kommer til dette, men jeg vil si at det som regel ikke finnes en bestemt fremgangsmåte for disse oppgavene, og at det er det som gjør de så artige (vanskelige) å løse. Likevel finnes det en del metoder som går igjen, som for eksempel å faktorisere, finne største felles divisor, si noe om delelighet osv, så er trikset da å vite når man skal benytte seg av de forskjellige.

Forresten har du noen tips på hvordan man bør starte å lære seg å løse slike oppgaver? Er det bare å hive seg på og håpe på det beste? Eller kreves det en del spesifikke forkunnskaper for å løse dem? Hvor bør jeg liksom starte?

[Gustav]

Hei, jeg er håpløs på slike oppgaver. Finnes det en bestemt fremgangsmåte?

[tex]p^x=y^4+4\Leftrightarrow p^x=(y^2-2y+2)(y^2+2y+2)[/tex]

kommer ikke egentlig lenger.. utrykkene i parentesen må jo tydeligvis være større en null. men jeg er lost.. kommer ikke på noe mer .

Du har jo kommet veldig langt på vei bare ved å finne faktoriseringen; det gjenstår kun et par vurderinger før du er i mål.

Merk at forskjellen mellom faktorene på høyre side er lik $4y$, og derfor må deres største felles divisor også dele nettopp $4y$. Men ettersom $p$ er et odde primtall må også $y$ være odde, og da er ingen av $(y^2-2y+2)$ eller $(y^2+2y+2)$ odde heller, så faktorenes største felles divisor er odde (og divisor i $y$). Som sagt er $y$ odde, og dermed innbyrdes primisk med $2$, slik at ingen av faktorene er delelig med $y$ heller; de gir rest $2$ ved divisjon på $2$. Tilsammen får vi at $\gcd{(y^2-2y+2),(y^2+2y+2)}=1$

Det følger at enten $(y^2-2y+2)$ eller $(y^2+2y+2)$ er lik $1$ (de er alltid positive). Dette gir henholdsvis $y=1$ og $y=-1$, hvor den siste løsningen forkastes siden $y\in\mathbb{N}$. Eneste løsning er $(p,x,y)=(5,1,1)$.

Er ikke den mest erfarne her når det kommer til dette, men jeg vil si at det som regel ikke finnes en bestemt fremgangsmåte for disse oppgavene, og at det er det som gjør de så artige (vanskelige) å løse. Likevel finnes det en del metoder som går igjen, som for eksempel å faktorisere, finne største felles divisor, si noe om delelighet osv, så er trikset da å vite når man skal benytte seg av de forskjellige.

Løste den slik: Hvis x=1 må $y^2-2y+2=1$, så $y=1$ og $p=5$ er én løsning. Hvis x>1 må $y^2-2y+2\equiv y^2+2y+2\equiv 0\, \mod(p)$, men da vil $4y=(y^2+2y+2)-(y^2-2y+2)\equiv 0\,\mod(p)$. Siden $p$ er odde primtall er $4$ et invertibelt element i $\mathbb{Z}/(p)$, så $y\equiv 0\, \mod(p)$. Men da er $y^2+2y+2\equiv 2\, \mod(p)$, som er en motsigelse. Altså er eneste løsning $(p,x,y)=(5,1,1)$.

EDIT: Cruxet er selvsagt faktoriseringen til å begynne med, og resten er rett frem grunnleggende tallteori/moduloregning.

Nyttige ting i forbindelse med oppgaven:

For faktoriseringen kan vi bruke Sophie Germains identitet: https://www.artofproblemsolving.com/wik ... n_Identity
Definisjon på primtall : Dersom p er et primtall og p deler ab, så må p dele enten a eller b https://en.wikipedia.org/wiki/Prime_element#Definition
Delelighetsprinsipper: Dersom p deler a+b og p deler b, så må p dele a.

[Brahmagupta]

2) Løser vi ligningen for $y$ ender vi opp med $y=-(x+p)^2/(3x+2p)$. La nå $q$ være et primtall som
deler $(x+p)^2$ og $(3x+2p)$. Dermed $q|(x+p)$ slik at $q|p=3(x+p)-(3x+2p)$. Det vil si at $3x+2p=\pm1$
eller $3x+2p=\pm p$ for at $y$ skal være et heltall. $3x+2p=p$ gir ingen løsning siden $p>3$, men
$3x+2p=-p$ gir løsningen $(x,y)=(-p,0)$.

For at $3x+2p=1$ skal gi heltallig $x$ må $p\equiv 2 \mod{3}$ og tilsvarende for at $3x+2p=-1$ skal gi
heltallig $x$ må $p\equiv 1\mod{3}$. I det første tilfellet får vi $x=(1-2p)/3$ og i det andre $x=-(1+2p)/3$.
Settes disse verdiene inn i uttrykket for $y$ får vi henholdsvis $y=-(p+1)^2/9$ og $y=(p-1)^2/9$.

Oppsummert; hvis $p\equiv 1 \mod3$
$(x,y)=(-p,0)$ og $(x,y)=(-(1+2p)/3, (p-1)^2/9)$,
eller hvis $p\equiv 2 \mod3$
$(x,y)=(-p,0)$ og $(x,y)=((1-2p)/3,-(p+1)^2/9)$.

[stensrud]

2)

Fin løsning! Er det forresten noen som har hatt suksess med å løse noen av andregradslikningene i $x$ eller $p$? Kom bare fram til noen små delresultater som f. eks at $\gcd(x,y)\mid p^2$, og sto tilslutt bom fast.