Modulär ekvation

Det är sent, bara en första tanke.

Först började jag spana efter villkor på m och n, men det var ju fel, uttrycket ska gälla oavsett vilka m och n jag väljer. 

Då tittade jag på olika val av m och n. Säg att n = 6 och m = 12. Då stämmer ekvationen för alla x < 6.

Tar vi n = 6 och m = 9 så stämmer det fortfarande för alla x < 6

n = 6 och m = 7 ger att x < 6.

Har jag tänkt rätt? Går det att komma vidare? 

Jag frågade chat gpt och den löste uppgiften med hjälp av MGM, den fick dock annat svar än det i facit. 

Svaret i facit är x=a×n×m+r där a och r är heltal och 0≤r<

AntiPhysics skrev:

Jag frågade chat gpt och den löste uppgiften med hjälp av MGM, den fick dock annat svar än det i facit. 

Svaret i facit är x=a×n×m+r där a och r är heltal och 0≤r<

Om vi låter $x \equiv r \pmod n$ får vi även att $x \equiv r \pmod m$
Den första ekvationen säger att $x$ är $r$ mer än en multipel av $n$, så 
$x = nA + r$ för något heltal $A$. Den andra ekvationen säger att $x$ är $r$ mer än en multipel av $m$. Så $x = mB + r$, för något heltal $B$
Alltså är $x = nA + r = mB + r$. 
Men detta ger oss att $nA = mB$.
 
Kan du fortsätta härifrån?

Vill bara nämna också, det är bättre att använda riktiga räknare för att lösa matteekvationer, inte AI. Jag testade chatgpts förmåga att lösa integraler nyligen och den hittade på en massa saker som inte alls stämde. Detta är särskilt skadligt om man ber om hjälp eftersom det är svårare att misstagen som AI:n gör. En som är gratis och kraftfull är wolfram alpha, med lätt syntax (man kan essentiellt skriva meningar, typ "integrate x^2 from 0 to 1").
(I detta fall är det dock lite svårare att få en dator att lösa uppgiften då det är lite svårare att formulera detta problem till en räknare)

Marilyn skrev:

Det är sent, bara en första tanke.

Först började jag spana efter villkor på m och n, men det var ju fel, uttrycket ska gälla oavsett vilka m och n jag väljer. 

Då tittade jag på olika val av m och n. Säg att n = 6 och m = 12. Då stämmer ekvationen för alla x < 6.

Tar vi n = 6 och m = 9 så stämmer det fortfarande för alla x < 6

n = 6 och m = 7 ger att x < 6.

Har jag tänkt rätt? Går det att komma vidare? 

Jag tänkte vidare när jag gått till sängs och insåg att jag var fel ute. Bra du fick annan hjälp!

Jag förstår resonemanget, det var tydligt men har ingen aning hur jag ska fortsätta >_<

Tack ändå @Marilyn

Jag vågar spåna vidare. Take or leave.

Jag tycker det finns en ide med (n, m) = (6, 12) eller (6, 9) eller (6, 7). I det första fallet är m en multipel av n, i det andra har de gemensam delare 3, i det tredje är största gemensamma delare 1.

(1) n = 6, m = 12

x = 0,1,2,3,4,5,  12,13,14,15,16,17,  24,…,29,  36,…,41, osv

dvs x = Cm+r ; 0 ≤ r < n

(2) n = 6, m = 9

x = 0,1,2,3,4,5,   18,19,20,21,22,23,   36,37,38,39,40,41, osv

dvs x = 2km+r ; 0 ≤ r < n,  k heltal.

Var kom 2 från? 6 = 2*3 och 9 = 3*3

Detta bör undersökas. 

(2b) n = 15, m = 21

x = 0,1,2, …,14,  105,106, …,129,  210, …,224, osv

dvs x = 5km+r ; 0 ≤ r < n

Var kom 5 från? 15 = 5*3 och 21 = 7*3

Nu har jag en hypotes. Om n = QP och m = RP där P är största gemensam delare så

x = Qkm+r ; 0 ≤ r < n

Jag testar en till:

(2c) n = 20, m = 25

x = 0,1,…,19,     100,…,119,    200,…219, osv

x = 4km + r;   0 ≤ r < n,  k heltal

20 = 4*5,   25 = 5*5

(3) n = 6,  m = 7

x = 0,1,2,…,5,    42,43,…,47, osv

x = 6km + r;    0 ≤ r < n,  k heltal

Så jag har en Hypotes. 

(a) Om n är faktor i m så

x = km + r

(b) Om n inte är faktor i m så 

x = C km + r ;  

där C är den största faktorn i n som inte är faktor i m.

(0 ≤ r < n,   k heltal)

Jag har inte något bevis. Och jag tycker att (a) och (b) borde kunna klumpas ihop till ett enda samband. Men klockan går. 

Det jag egentligen ville förmedla var att denna typ av uppgifter tror jag man gärna angriper genom att prova sig fram. Enstaka exempel har noll bevisvärde, men när jag tycker mig ana ett samband så hjälper de mig formulera ett bevis.

PS Jag kollade din uppgift från facit, x = amn + r.

Det förstår jag inte. Om n = 6 och m = 12 så ger det

x = 0,1,2,3,4,5,    72,73,74 osv

men x = 12 och 13 borde väl duga?? Antingen har jag inte förstått (mest troligt), eller så har facit fel.

Marilyn skrev:

Jag vågar spåna vidare. Take or leave.

Jag tycker det finns en ide med (n, m) = (6, 12) eller (6, 9) eller (6, 7). I det första fallet är m en multipel av n, i det andra har de gemensam delare 3, i det tredje är största gemensamma delare 1.

(1) n = 6, m = 12

x = 0,1,2,3,4,5,  12,13,14,15,16,17,  24,…,29,  36,…,41, osv

dvs x = Cm+r ; 0 ≤ r < n

(2) n = 6, m = 9

x = 0,1,2,3,4,5,   18,19,20,21,22,23,   36,37,38,39,40,41, osv

dvs x = 2km+r ; 0 ≤ r < n,  k heltal.

Var kom 2 från? 6 = 2*3 och 9 = 3*3

Detta bör undersökas. 

(2b) n = 15, m = 21

x = 0,1,2, …,14,  105,106, …,129,  210, …,224, osv

dvs x = 5km+r ; 0 ≤ r < n

Var kom 5 från? 15 = 5*3 och 21 = 7*3

Nu har jag en hypotes. Om n = QP och m = RP där P är största gemensam delare så

x = Qkm+r ; 0 ≤ r < n

Jag testar en till:

(2c) n = 20, m = 25

x = 0,1,…,19,     100,…,119,    200,…219, osv

x = 4km + r;   0 ≤ r < n,  k heltal

20 = 4*5,   25 = 5*5

(3) n = 6,  m = 7

x = 0,1,2,…,5,    42,43,…,47, osv

x = 6km + r;    0 ≤ r < n,  k heltal

 

Så jag har en Hypotes. 

(a) Om n är faktor i m så

x = km + r

(b) Om n inte är faktor i m så 

x = C km + r ;  

där C är den största faktorn i n som inte är faktor i m.

(0 ≤ r < n,   k heltal)

 

Jag har inte något bevis. Och jag tycker att (a) och (b) borde kunna klumpas ihop till ett enda samband. Men klockan går. 

Det jag egentligen ville förmedla var att denna typ av uppgifter tror jag man gärna angriper genom att prova sig fram. Enstaka exempel har noll bevisvärde, men när jag tycker mig ana ett samband så hjälper de mig formulera ett bevis.

 

PS Jag kollade din uppgift från facit, x = amn + r.

Det förstår jag inte. Om n = 6 och m = 12 så ger det

x = 0,1,2,3,4,5,    72,73,74 osv

men x = 12 och 13 borde väl duga?? Antingen har jag inte förstått (mest troligt), eller så har facit fel.

Det verkar finnas något fel, ja

Vi har att $x = c_1 n + r = c_2m + r$ där $c_1$ och $c_2$ är två heltal. 

Då har vi att $c_1 n = c_2 m$. Det facit säger är att detta medför att $x = c_3 nm$ för något heltal $c_3$. Detta bygger säkert på den elementära satsen

"Om ett primtal $p$ delar $ab$ måste $p|a$ eller $p|b$".

Det facit verkar försöka säga från likheten $c_1 n = c_2 m$ är att "$m$ delar högerledet så $m$ måste dela vänsterledet. Eftersom $m > n$ har vi $m \nmid n$, så $m|c_1$. Då får vi att $c_1 = m c_3$ för något heltal $c_3$ och då är $c_1 n = c_3 n m$."

Denna logik är felaktig eftersom vi kan ha att en primtalsfaktor av $m$ finns i $n$, medan resten av $m$:s faktorer finns i $c_1$. Då faller detta argument. Det fungerar bara om $m$ och $n$ inte delar primtalsfaktorer.

Om vi har $n = 4$ och $m=7$ fungerar det
Exempel: $x = 59$
$59 \equiv 3 \pmod 4$, $59 \equiv 3 \pmod 7$
$x = 7 \cdot 8 + 3 = 7 \cdot 4 \cdot 4 +3= 4nm +3$.

Istället låter vi $n = 4$ och $m = 8$ och $x=59$. Nu delar $m$ och $n$ primtalsfaktorer. 
$59 \equiv 3 \pmod 4$, $59 \equiv 3 \pmod 8$. 
$59 = 8 \cdot 7 + 3$. Men nu ser vi att vi inte kan skriva detta som facit vill. Enligt facit ska vi kunna skriva $8 \cdot 7$ som $n\cdot m\cdot a$ för något heltal $a$. Men $n\cdot m\cdot a = 32a$. Så $32a = 8 \cdot 7$. Det finns inga heltalslösningar till denna ekvation. 

Jag tänkte vidare idag.

Jag gissar att du beräknat minsta gemensam nämnare ibland:

E/6 + F/12 = (…)/12

E/6 + F/9 = (…)/18

E/6 + F/7 = (…)/42 

Detta tycks vara samma sak. Vi bestämmer det minsta talet som är delbart med n och m.

Kalla det för C. Då är

x = Ck + r     0 ≤ r < n     k och r heltal.

(Det är frestande att kalla C minsta gemensamma nämnaren till 1/n + 1/m, men litet vanskligt eftersom uppgiften inte har några bråk. Nuförtiden drillar man inte bråkräkning lika mycket som förr, men för en äldre generation är MGN ett cementerat begrepp.)

Marilyn skrev:

Jag tänkte vidare idag.

Jag gissar att du beräknat minsta gemensam nämnare ibland:

E/6 + F/12 = (…)/12

E/6 + F/9 = (…)/18

E/6 + F/7 = (…)/42 

Detta tycks vara samma sak. Vi bestämmer det minsta talet som är delbart med n och m.

Kalla det för C. Då är

x = Ck + r     0 ≤ r < n     k och r heltal.

(Det är frestande att kalla C minsta gemensamma nämnaren till 1/n + 1/m, men litet vanskligt eftersom uppgiften inte har några bråk. Nuförtiden drillar man inte bråkräkning lika mycket som förr, men för en äldre generation är MGN ett cementerat begrepp.)

Ja, det borde den korrekta lösningen till problemet