23 svar
192 visningar
naytte behöver inte mer hjälp
naytte 4896 – Moderator
Postad: 7 jan 16:37 Redigerad: 7 jan 16:40

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

Uppgiften lyder:

Låt T(n)=n2+3n+11. Visa att 49 aldrig är en delare till talet, oavsett vilket n man väljer.

Nu står det inte explicit i uppgiften men av nyvunnen erfarenhet antar jag att n är ett heltal.

Jag har inte den blekaste om hur man skulle kunna komma igång här. Jag tänkte först att man kunde göra ett motsägelsebevis á la "visa att om det finns ett n som gör det delbart med 49 kan detta n inte vara ett heltal", men jag kom inte riktigt någonstans med det.

Jag misstänker att man kan använda kongruens för att lösa detta men det är jag urkass på. Så om någon har tips på hur man kan göra det är jag all ears!

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

naytte 4896 – Moderator
Postad: 7 jan 17:31

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?"

nigus 52
Postad: 7 jan 17:38

Du vill visa att ekvationen

n2+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

Visa spoiler

Ekvationen är en andragradare, och det funkar bra att kvadratkomplettera även när man räknar modulo (så länge inverser finns i alla fall):

(n2+3/2)2 = 94-11

(ett användbart trick är att 2^{-1} = (M+1)/2 modulo M, så du behöver inte krångla med euklides här)

Problemet kommer i sista steget när vi måste dra roten ur. Det finns inga generella algoritmer för att dra roten ur som i princip är snabbare än att kolla alla 49 rester. Så lösningen kommer antagligen inte vara någon generell metod, utan vi kommer behöva utnyttja något specifikt för just den här ekvationen eller talet 49. 

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

naytte 4896 – Moderator
Postad: 7 jan 17:43

@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!

Yngve 40157 – Livehjälpare
Postad: 7 jan 17:45 Redigerad: 7 jan 17:48
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.

nigus 52
Postad: 7 jan 17:55
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:

n=10 (mod 49)  n2+3n+11 =102+30+11=141=2*49+43=430 (mod 49)

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.

naytte 4896 – Moderator
Postad: 7 jan 17:59 Redigerad: 7 jan 18:06

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"?

nigus 52
Postad: 7 jan 18:00
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

naytte 4896 – Moderator
Postad: 7 jan 18:02

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

nigus 52
Postad: 7 jan 18:15 Redigerad: 7 jan 18:15
naytte skrev:

Okej. Men varför betraktar vi bara vad resten för n blir vid division med 49 och inte hela polynomet n2+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.

naytte 4896 – Moderator
Postad: 7 jan 18:19 Redigerad: 7 jan 18:21

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

n4910\displaystyle n\equiv _{49}10 så medför detta att resten hos n2 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])?

nigus 52
Postad: 7 jan 18:30
naytte skrev:

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

n4910\displaystyle n\equiv _{49}10 så medför detta att resten hos n2 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])?

n2 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)

naytte 4896 – Moderator
Postad: 7 jan 18:32

Men i din ursprungliga lösning där du lät: n4910\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?

nigus 52
Postad: 7 jan 18:41
naytte skrev:

Men i din ursprungliga lösning där du lät: n4910\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 a  och  y b    så är  x+ya+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 xr  och p(x) är ett polynom med heltalskoefficienter, så är p(x)p(r) (modulo m)

naytte 4896 – Moderator
Postad: 7 jan 18:44 Redigerad: 7 jan 18:48

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 n4910T(n)49T(10)\displaystyle n\equiv _{49}10\implies T(n)\equiv _{49}T(10) ?

nigus 52
Postad: 7 jan 19:02
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 n4910T(n)49T(10)\displaystyle n\equiv _{49}10\implies T(n)\equiv _{49}T(10) ?

exakt

naytte 4896 – Moderator
Postad: 7 jan 19:07 Redigerad: 7 jan 19:21

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å?

nigus 52
Postad: 7 jan 21:59
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:

Visa spoiler 49 = 72. Det är en bra idé att kolla vilka rester polynomet kan ha modulo 7 istället. Tänk om polynomet aldrig är delbart med 7 ens, då skulle vi ju vara klara. Men även om vi inte har sån tur så kommer undersökningen att ge mer information om vad n behöver vara för att polynomet ska kunna vara delbart med 49, och då kan vi få till en motsägelse förhoppningsvis...
naytte 4896 – Moderator
Postad: 7 jan 22:23

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

naytte 4896 – Moderator
Postad: 8 jan 18:05 Redigerad: 8 jan 18:06

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 k2+3k+11 inte är delbart med 49. Men jag tänker att 2k+1 och k2+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?

naytte 4896 – Moderator
Postad: 9 jan 22:49

Bump.

Laguna Online 30252
Postad: 10 jan 09:10

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.

 

SvanteR 2737
Postad: 10 jan 14:13

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 72=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!

Svara
Close