Bestäm alla primtal så att uttrycket blir ett primtal

Detta problemet kommer från årets upplaga av skolornas Matematiktävling, som jag själv deltog i. Jag resonerade så här:

För att $p^q+q^p$ ska vara ett primtal krävs först och främst att det är ojämnt (eftersom det är summan av två primtal är det större än det enda jämna primtalet). Det enda sättet för en summa av två tal att bli ojämn är om ett av talen är ojämnt och ett är jämnt (för att försäkra sig om detta kan man studera $2m+2n$, $2m+2n+1$ och $2m+1+2n+1$). Vi vet alltså att det ena primtalet är jämnt.

Det enda sättet för en potens att vara jämn är om basen är jämn (annars kan det ju inte ha en faktor av två). Eftersom det enda jämna primtalet är $2$ drar man slutsatsen att talet är på formen $2^q+q^2$. Härifrån blev det dock lite klurigare. Jag började helt enkelt med att spalta upp de första möjligheterna:

Det enda primtalet jag kunde hitta var $17$, resten av talen blev delbara med $3$. Detta ledde mig till att undersöka kongruensen modulo $3$. Jag delade upp i tre fall:

Fall 1: $q\equiv0\ (\text{mod}\ 3)$

Kongruenslagarna ger:

$2^q+q^2\equiv2^q+0\ (\text{mod}\ 3)$

Efter lite funderande kom jag på att $2\ (\text{mod}\ 3)$ också kan skrivas som $-1\ (\text{mod}\ 3)$, vilket gör den vänstra potensen väldigt enkel:

$2^q\equiv(-1)^q\ (\text{mod}\ 3)$, och då $q$ är ojämnt får man:

$2^q+q^2\equiv-1\ (\text{mod}\ 3)\equiv2\ (\text{mod}\ 3)$

Här får man alltså ett tal som inte delbart med tre, men det enda primtalet som uppfyller detta fall är $3$ (eftersom alla andra primtal inte får vara delbara med tre). Paret $(2,3)$ är alltså en lösning till problemet.

Fall 2: $q\equiv1\ (\text{mod}\ 3)$

På samma sätt ger kongruenslagarna:

$2^q+q^2\equiv2^q+1\ (\text{mod}\ 3)$

Återigen skriver vi $2\ (\text{mod}\ 3)$ som $-1\ (\text{mod}\ 3)$:

$2^q+1\equiv(-1)^q+1\ (\text{mod}\ 3)$

Och eftersom $q$ är ojämnt får vi:

$2^q+q^2\equiv0\ (\text{mod}\ 3)$

vilket bevisar att $2^q+q^2$ är delbart med tre för detta fall, och alltså inte ett primtal.

Fall 3: $q\equiv2\ (\text{mod}\ 3)$

Samma metod som för föregående fall ger att:

$2^q+q^2\equiv0\ (\text{mod}\ 3)$

vilket visar att det inte heller finns några primtal på formen $2^q+q^2$ för detta fall.

Man kan alltså dra slutsatsen att det enda paret som fungerar är $(2,3)$.

Hej

Jag skrev själv skolans matematiktävling i måndags och det var fråga 3 på provet. Nu i efterhand när man kollar på t.ex. AlvinB svar skulle jag nog lägg till saker för att förtydliga :D.

Det var en intressant uppgift. Lösningar och uppgifterna skulle släpas den 5 Oktober, men dom har fortfarande inte släppts. När det släpps tipsar jag dig att kolla på den sista uppgiften. Den var något extra att bita i jämfört mot dom andra 5 uppgifterna.

jonis10 skrev:

Hej

Jag skrev själv skolans matematiktävling i måndags och det var fråga 3 på provet. Nu i efterhand när man kollar på t.ex. AlvinB svar skulle jag nog lägg till saker för att förtydliga :D.

Det var en intressant uppgift. Lösningar och uppgifterna skulle släpas den 5 Oktober, men dom har fortfarande inte släppts. När det släpps tipsar jag dig att kolla på den sista uppgiften. Den var något extra att bita i jämfört mot dom andra 5 uppgifterna.

Vill minnas att det stod femte november på pappret. Varför man väntar så länge med att släppa lösningarna vet jag inte.

Du kanske är lite mer insatt i hur tävlingen fungerar så jag passar på att fråga:

Är det meningen att gymnasieelever som går sitt första år (exempelvis mig själv) och bara läst högstadiematematik ska kunna lösa dessa problem? Jag lyckades lösa några av uppgifterna, men jag hade varit chanslös om jag inte hade fritidsläst om exempelvis kongruensräkning.

AlvinB skrev:

jonis10 skrev:

Hej

Jag skrev själv skolans matematiktävling i måndags och det var fråga 3 på provet. Nu i efterhand när man kollar på t.ex. AlvinB svar skulle jag nog lägg till saker för att förtydliga :D.

Det var en intressant uppgift. Lösningar och uppgifterna skulle släpas den 5 Oktober, men dom har fortfarande inte släppts. När det släpps tipsar jag dig att kolla på den sista uppgiften. Den var något extra att bita i jämfört mot dom andra 5 uppgifterna.

Vill minnas att det stod femte november på pappret. Varför man väntar så länge med att släppa lösningarna vet jag inte.

Du kanske är lite mer insatt i hur tävlingen fungerar så jag passar på att fråga:

Är det meningen att gymnasieelever som går sitt första år (exempelvis mig själv) och bara läst högstadiematematik ska kunna lösa dessa problem? Jag lyckades lösa några av uppgifterna, men jag hade varit chanslös om jag inte hade fritidsläst om exempelvis kongruensräkning.

 Femte november stämmer nog när jag tänker efter. Jag tycker också de är lite konstigt att man behöver vänta i över en månad på lösningarna, eftersom proven skickas in till arrangörerna för rättning. Antar att det har något med fusk eller liknande och göra.

Jag skrev själv det första året och märkte att en del teori saknades för att man ska kunna ha en chans. Jag tror nog att dom förutsätter att dom personerna som anmäler sig har en god matematiks bakgrund och att eleven studerar matematik utöver gymnasiematematik. Har för mig att Hugo Eberhard som lyckades vinna för året och även lyckades kvala till finalen redan i Åk 9.

För nyfikenhetens skull lyckades du lösa sista uppgiften? Personligen satt jag på geometri uppgiften ett bra tag, sen gick jag över till sista uppgiften och då sa huvudet ifrån :D. 

Om du menar den om biljardbordet så nej. Jag tror att det är något i själva reglerna för hur bollen studsar jag inte begriper eftersom jag inte kan förstå hur uttrycket kan ha antalet studsar (och inte sidlängden) under roten. Men vi skall väl inte kapa denna tråd för att prata om en annan uppgift. :-)

Bra Alvin,

Du har redan visat det som i förbigående, men det kan vara värt att poängtera att kvadraten av ett primtal större än tre alltid ger resten 1 vid division med 3, dvs $q^2 \equiv 1 \pmod{3}$ för alla primtal $q>3$.

Som du noterar lämnar 2 upphöjt till ett udda tal resten -1 och vi får

$2^q+q^2\equiv 0 \pmod{3}$

för alla primtal $q>3$

Jag tänkte mig fram till Guggles regel via Fermats lilla sats men finns kanske ett primtalsspecifikt bevis också.

Ja, nya trådar, är ju tydligen regeln numera även om jag inte skulle anmärka på en sådan kapning särskillt som jag tycker biljarder generellt är ett kul problem. (Skrev min kanduppsats om biljarder även om det var ett ganska dåligt verk)

I alla fall som jag inte själv har pappret.

För en populärmatematisk antydan om att det finns mycket även praktisk matematik där kan vi ta en av segmenten från Disneys Mattemagifilm från 50-talet. http://www.youtube.com/watch?v=U_ZHsk0-eF0&t=15m55s Även om det är ett sidospår.

Guggle skrev:

Bra Alvin,

Du har redan visat det som i förbigående, men det kan vara värt att poängtera att kvadraten av ett primtal större än tre alltid ger resten 1 vid division med 3, dvs $q^2 \equiv 1 \pmod{3}$ för alla primtal $q>3$.

Som du noterar lämnar 2 upphöjt till ett udda tal resten -1 och vi får

$2^q+q^2\equiv 0 \pmod{3}$

för alla primtal $q>3$

 Ja, det var kanske lite lat av mig att inte uttryckligen skriva det. Det är ju i alla fall ganska enkelt att visa med kongruenslagarna eftersom primtal större än $3$ är kongruenta med $1$ eller $2\ \pmod{3}$ och $1^2\equiv1\ \pmod{3}$ och $2^2\equiv1\ \pmod{3}$.

SeriousCephalopod skrev:

Ja, nya trådar, är ju tydligen regeln numera även om jag inte skulle anmärka på en sådan kapning särskillt som jag tycker biljarder generellt är ett kul problem. (Skrev min kanduppsats om biljarder även om det var ett ganska dåligt verk)

I alla fall som jag inte själv har pappret.

Jag har problemet nedskrivet, bara att fråga om du är intresserad.