Visa att talen som ges av funktionen aldrig är delbara med 49.

Jag skulle nog prova med ett induktionsbevis här. :)

Induktion, ja det skulle kanske fungera.

Men det känns lite märkligt. Hittills har jag bara använt induktion för att visa ATT påståenden stämmer, inte att de INTE stämmer. Vad skulle den induktiva hypotesen vara då? "Antag att 49 inte är en delare till polynomet T?"

Du vill visa att ekvationen

$n^2+3n+11=0 (mod 49)$

inte har några lösningar. En möjlig lösning är att testa att låta n vara alla 49 möjliga rester modulo 49, och se att vänsterledet aldrig blir 0. Det är ju väldigt jobbigt, men det är alltid skönt att veta att det finns en lösning som i alla fall går att utföra för hand:)

Lite andra saker att notera

(säg till om du vill ha fler ledtrådar)

@nigus

Vad exakt menar du med:

En möjlig lösning är att testa att låta n vara alla 49 möjliga rester modulo 49, och se att vänsterledet aldrig blir 0 

Som sagt är jag urkass på det där med kongruenser. Så om du skulle kunna ge ett exempel på vad du menar vore det guld värt!

naytte skrev:

Induktion, ja det skulle kanske fungera.

[...]

Vad skulle den induktiva hypotesen vara då? "Antag att 49 inte är en delare till polynomet T?"

Typ så här:

Induktionsbas:

T(0) = 11 är ej delbart med 49.

Induktionsantagande:

Antg att T(n) ej är delbart med 49.

Induktionssteg:

Visa att om T(n) ej är delbart med 49 så ör ej heller T(n+1) delbart med 49.

Extra induktionssteg för negativa n:

Visa att om T(n) ej är delbart med 49 så ör ej heller T(n-1) delbart med 49.

naytte skrev:

@nigus

Vad exakt menar du med:

En möjlig lösning är att testa att låta n vara alla 49 möjliga rester modulo 49, och se att vänsterledet aldrig blir 0 

Som sagt är jag urkass på det där med kongruenser. Så om du skulle kunna ge ett exempel på vad du menar vore det guld värt!

Du kan se det som att vi delar upp lösningen i 49 fall, beroende på vad för rest n har modulo 49. Till exempel rest 10 skulle kunna se ut så här:

$$\begin{gathered} n=10 (mod 49) \\ \Rightarrow n^2+3n+11 =\hspace{0.17em}{10}^2+30+11=141=2*49+43=43\ne 0 (mod 49) \end{gathered}$$

så vänsterledet får alltid en rest av 43 och kan därmed aldrig vara en multipel av 49, om n har resten 10 modulo 49. Sedan är det bara att kolla alla 48 kvarvarande rester:)

Det skulle som sagt vara väldigt jobbigt att faktiskt lösa problemet så här även om det vore möjligt under en tenta till exempel. Det finns betydligt bättre lösningar men de enda jag kan se just nu kräver en del mer tricks.

Jag tror jag saknar elementär kunskap om kongruenser för att hänga med på exakt vad du menar. Du skriver ex. n=10 (mod 49). Ska det verkligen vara ett likhetstecken där eller ska det vara "kongruenstecknet"?

naytte skrev:

Jag tror jag elementär kunskap om kongruenser för att hänga med på exakt vad du menar. Du skriver ex. n=10 (mod 49). Ska det verkligen vara ett likhetstecken där eller ska det vara "kongruenstecknet"?

kongruenstecken ska det vara, det stämmer

Okej. Men varför betraktar vi bara vad resten för n blir vid division med 49 och inte hela polynomet n²+3n+11?

naytte skrev:

Okej. Men varför betraktar vi bara vad resten för n blir vid division med 49 och inte hela polynomet n²+3n+11?

På den andra raden i exempeluträkningen så räknade jag ut vad polynomets rest blev, det blev 43 om n:s rest var 10. De andra likhetstecknen ska också vara kongruenstecken:) (man brukar ofta slarva med det)

Men frågan är kanske snarare "varför är strategin att kolla alla möjliga rester hos n och inte alla möjliga rester hos polynomet?" Det vi ska visa är att polynomet inte kan ha rest 0 oavsett vad n är för heltal, därför är det en bra strategi att låta n vara det vi varierar i lösningen, och sedan se vad som händer med polynomet.

Om vi istället skulle göra tvärtom och testa alla polynomets rester skulle vi bara få påståenden som "om polynomet har rest 0 så har polynomet rest 0", och det hjälper oss inte att lösa problemet.

Okej. Jag är nog med på strategin men jag förstår inte varför den fungerar. Är det så att om:

$\displaystyle n\equiv _{49}10$ så medför detta att resten hos n² vid division med 49 blir 100?

Dvs. om du låter resten hos n vara något tal kan du räkna fram polynomets totala rest (mod [det talet])?

naytte skrev:

Okej. Jag är nog med på strategin men jag förstår inte varför den fungerar. Är det så att om:

$\displaystyle n\equiv _{49}10$ så medför detta att resten hos n² vid division med 49 blir 100?

Dvs. om du låter resten hos n vara något tal kan du räkna fram polynomets totala rest (mod [det talet])?

n² blir kongruent med 100 modulo 49 ja, men resten är alltid ett tal mellan 0 och 48. I det här fallet skulle resten bli 100-2*49=2.

Det du skrev på sista raden är nästan rätt:

Om du låter resten hos n (mod 49) vara något tal kan du räkna fram polynomets totala rest (mod 49)

Men i din ursprungliga lösning där du lät: $\displaystyle n\equiv _{49}10$ stoppade du så att säga "in" 10 i polynomet. Varför gjorde du det och varför fungerar det?

naytte skrev:

Men i din ursprungliga lösning där du lät: $\displaystyle n\equiv _{49}10$ stoppade du så att säga "in" 10 i polynomet. Varför gjorde du det och varför fungerar det?

Det finns en massa räkneregler för moduloräkning, till exempel

om $x \equiv a och y \equiv b så är x+y\equiv a+b (mod m)$

Liknande regler finns för multiplikation och potenser. En följd av detta är att man kan räkna ut ett polynoms rest genom att stoppa in variabelns rest och bara räkna på som vanligt:

om $x\equiv r och p\left(x\right) är ett polynom med heltalskoefficienter, så är p\left(x\right)\equiv p\left(r\right) (modulo m)$

Ja okej. Bara vid första anblick ser det ut att vara en följd av faktorsatsen. Häftigt.

Så i detta fall har vi att $\displaystyle n\equiv _{49}10\implies T(n)\equiv _{49}T(10)$ ?

naytte skrev:

Ja okej. Bara vid första anblick ser det ut att vara en följd av faktorsatsen. Häftigt.

Så i detta fall har vi att $\displaystyle n\equiv _{49}10\implies T(n)\equiv _{49}T(10)$ ?

exakt

Och eftersom resten då 141 delas med 49 inte är 0 vet vi att polynomet inte är delbart med 49 då n har resten 10 vid division med 49?

Och de enda resterna n skulle kunna ha vid division med 49 är 0-49. Så då kan man testa allihopa och få alla möjliga rester på polynomet också?

naytte skrev:

Och eftersom resten då 141 delas med 49 inte är 0 vet vi att polynomet inte är delbart med 49 då n har resten 10 vid division med 49?

Och de enda resterna n skulle kunna ha vid division med 49 är 0-49. Så då kan man testa allihopa och få alla möjliga rester på polynomet också?

Japp.

Här är en ledtråd för en mindre tidskrävande lösning:

Okej. Då är jag nog med.

Men jag förstår fortfarande inte riktigt varför vi bara kollar på n:s möjliga rester. Hur vet vi att vi har kollat alla fall vi behöver då vi bara tittar på n och inte på hela polynomet?

Tillägg: 8 jan 2024 18:56

Jag fattar nu. Har varit väldigt trött på senaste så var lite trög. Eftersom n kan vara vilket tal som helst kan det bara ha de resterna. Tack för hjälpen med kongruens! @nigus

Jag gjorde en ansats nu med ett induktionsbevis och har kommit fram till följande:

Men jag vet inte exakt hur man ska hantera "2k+1". För vi vet ju enligt vårt induktionsantagande att k²+3k+11 inte är delbart med 49. Men jag tänker att 2k+1 och k²+3k+11 kanske kan få rester som "tar ut varandra" eller tillsammans blir ett heltal. Hur visar jag att det aldrig kan hända?

Några bra förslag?

Bump.

Du har tappat bort +3 sist, så det blir 2k+4, men jag tror inte det hjälper.

Om man vet att resten tillhör en viss mängd av tal (som inte innehåller 0), och kan visa med induktionssteget att nästa rest också ingår i den mängden, så fungerar induktionsbeviset. Då får man ta reda på hela den mängden först. Det är antagligen något enklare än att räkna ut resten för alla 49 värden på n mod 49.

Tillägg: 10 jan 2024 09:51

Det var ju inte något bra förslag, det var bara en kommentar.

Jag gör på ett annat sätt: kollar först resterna modulo 7, kommer på något, och använder det med modulo 49.

Jag funderade lite på induktionsbevis men kom ingenvart. I stället föreslår jag en metod som liknar den som nigus är inne på. Så här tänker jag:

Alla tal som är delbara med 49 är även delbara med 7 eftersom 7²=49. Om du kan visa att T(n) inte är delbart med 7 är du alltså klar.

Sedan kommer vi till något som man kanske inte går igenom i Ma5, nämligen restklasser. När man dividerar ett heltal med 7 finns det bara 7 möjliga rester man kan få, nämligen 0, 1, 2, 3, 4, 5 eller 6. Det betyder att alla heltal n kan skrivas på något av följande sätt:

n = 7m + 0

n = 7m + 1

n = 7m + 2

n = 7m + 3

n = 7m + 4

n = 7m + 5

n = 7m + 6

där m är ett heltal. Detta kallas för att man kan dela in heltalen i restklasser.

Sedan får du pröva de olika alternativen. Det enklaste är att du skriver n = 7m + r. Sedan sätter du in 7m + r i uttrycket och utvecklar. Därefter kan du pröva med r från 0 till 6 och se om du kan visa att inget av resultaten kan delas med 7. Fråga igen om detta inte räcker!