Svår uppgift gällande modulo beräkning...

Vi ser vilka tal vi kan dividera jämnt med och inte. Om vi låter antalet personer på företaget (där vi ignorerar de 10 som inte kommer vara med) vara $n$. Vad blir resten när vi delar $n$ med $4, 8, 3, 6, 9, 5$ och $7$?

vid division med 4 och 8 blir resten 1, vid division med 5 och 7 blir resten 0 och vid division med 3,6 och 9 blir resten -1

Om du tänker på primtalsfaktoriseringen av $n$, så måste faktorerna 5 och 7 ingå. Samtidigt kan inte 3 ingå, och max en 2:a kan ingå. Det begränsar ganska kraftigt vilka möjliga faktorer $n$ kan ha om $490\leq n \leq 790$.

"och max en 2:a kan ingå"

Resten vid division med 4 och 8 är 1. Så, $n$ är ett udda tal. Ingen 2:a kan ingå.

Ja, precis. Ska man sedan testa sig fram eller teckna ett ekvationssystem?

Jag hade testat mig fram. Eftersom det ska vara delbart med 5 och 7 vill du bara testa tal på formen 35*n. Och vi vet att det är ett udda tal, så inga jämna n behöver testas. Vilket är det minsta n du vill testa ifrån? 

Juste, talet måste vara en multipel av 35. Däremot ska ju tio personer inte delta och antalet personer är kongruent med 1 mod 8. Det måste jag väl också använda?

Det med att lägga till 10 gör du på slutet, det är minsta problemet. När du har kommit fram till vilka n du vill testa behöver du testa alla extra krav, tex att det är 1 mod 8, men ta ett steg i taget. 

De där tio påverkar också vilka lösningar som är OK. I det här fallet skulle 495 kunna ingå som antalet indelade i grupper. Ja, nu är det ju inte en multipel av 35, men rent principiellt. 

Ok, så alltså ska man testa alla tal i det givna intervallet som uppfyller samtliga kriterier? Facit visade nämligen hur problemet kan lösas genom att ställa upp ekvationer, men jag förstår inte hur facit kommer fram till dessa. Hur skulle man kunna lösa med ekvationer?

Det är inte många att testa.

Man söker $n$ så att

• $n \equiv 1 \quad(\mod 4)$
• $n \equiv 1 \quad(\mod 8)$
• $n \equiv -1 \quad(\mod 3)$
• $n \equiv -1 \quad(\mod 6)$
• $n \equiv -1 \quad(\mod 9)$
• $n \equiv 0 \quad(\mod 5)$
• $n \equiv 0 \quad(\mod 7)$

De sista två raderna medför att $n$ är delbart med 35, så $n = 35k$, där $k$ är ett positivt heltal.

Notera att $35 \equiv -1 \quad(\mod 9)$ (och även mod 6 och mod 3, men det bortser jag ifrån nu).

Därmed är $n = 35k \equiv -k \quad (\mod 9)$. Man vill att detta blir $-1 \quad (\mod 9)$, vilket innebär att $k=9l+1$, där $l$ är ett naturligt tal, d.v.s. $k=1$, $k=10$, $k=19$, eller $k=28$ (eller ännu högre).

• $k=1$ ger $n=35$, vilket är för få
• $k=10$ ger $n=350$, vilket är för få
• $k=19$ ger $n=665$, vilket ligger i det önskade intervallet. Notera att $n=665$ uppfyller ALLA kraven på rest vid division med 3,4,5,6,7,8,9
• $k=28$ ger $n=1330$, vilket är för mycket

Företaget har 665+10 = 675 anställda.

Om man inte ville pröva dessa $k$-värden, så kan man sätta in $k=9l+1$ i formeln för $n$ och bestämma rester vid divisioner. Man får $n=35k = 35(9l+1) = 315l + 35$, där

• $315 \equiv -1 \quad(\mod 4)$ och $35 \equiv -1 \quad(\mod 4)$, så $n \equiv -l-1 \quad(\mod 4)$
• $315 \equiv 3\quad(\mod 8)$ och $35 \equiv 3 \quad(\mod 8)$, så $n \equiv 3l+3 \quad(\mod 8)$ 
• $315 \equiv 0 \quad(\mod 3)$, så $n \equiv 0l-1 \quad(\mod 3)\equiv -1\quad(\mod 3)$
• $315 \equiv 3 \quad(\mod 6)$, så $n \equiv 3l-1 \quad(\mod 6)$
• $315 \equiv 0 \quad(\mod 9)$, så så $n \equiv 0l-1 \quad(\mod 9)$

Av allt detta fick man tre krav på $l$:

• $-l-1 \equiv 1 \quad (\mod 4) \iff l \equiv 2 \quad(\mod 4)$, 
• $3l+3 \equiv 1 \quad (\mod 8) \iff 3l \equiv -2\quad(\mod 8) \iff l \equiv 2\quad(\mod 8)$
• $3l-1 \equiv -1 \quad (\mod 6) \iff 3l \equiv 0\quad(\mod 6) \iff l$ är jämnt

Totalt är $l=8j + 2$ där $j$ är ett naturligt tal. När detta sätts in i formeln för $n$, så får man att

$n = 315l+35 = 315(8j + 2) + 35 = 2520j + 665$.

Här ser man direkt att $j=0$ önskas för att hamna i rätt intervall

arad1986 skrev:

"och max en 2:a kan ingå"

Resten vid division med 4 och 8 är 1. Så, $n$ är ett udda tal. Ingen 2:a kan ingå.

Jag använde bara att talet inte är delbart med 4. Det finns ju så klart mycket mer att säga om talet än vad jag angav i min ledtråd.

Har ni lärt er att lösa diofantiska ekvationer, som t.ex. 35a - 8b = 1?

Nej, tyvärr inte än. Det kommer i senare kapitel. 

LuMa07 skrev:

Det är inte många att testa.

Man söker $n$ så att

• $n \equiv 1 \quad(\mod 4)$
• $n \equiv 1 \quad(\mod 8)$
• $n \equiv -1 \quad(\mod 3)$
• $n \equiv -1 \quad(\mod 6)$
• $n \equiv -1 \quad(\mod 9)$
• $n \equiv 0 \quad(\mod 5)$
• $n \equiv 0 \quad(\mod 7)$

De sista två raderna medför att $n$ är delbart med 35, så $n = 35k$, där $k$ är ett positivt heltal.

Notera att $35 \equiv -1 \quad(\mod 9)$ (och även mod 6 och mod 3, men det bortser jag ifrån nu).

Därmed är $n = 35k \equiv -k \quad (\mod 9)$. Man vill att detta blir $-1 \quad (\mod 9)$, vilket innebär att $k=9l+1$, där $l$ är ett naturligt tal, d.v.s. $k=1$, $k=10$, $k=19$, eller $k=28$ (eller ännu högre).

• $k=1$ ger $n=35$, vilket är för få
• $k=10$ ger $n=350$, vilket är för få
• $k=19$ ger $n=665$, vilket ligger i det önskade intervallet. Notera att $n=665$ uppfyller ALLA kraven på rest vid division med 3,4,5,6,7,8,9
• $k=28$ ger $n=1330$, vilket är för mycket

Företaget har 665+10 = 675 anställda.

---

Om man inte ville pröva dessa $k$-värden, så kan man sätta in $k=9l+1$ i formeln för $n$ och bestämma rester vid divisioner. Man får $n=35k = 35(9l+1) = 315l + 35$, där

• $315 \equiv -1 \quad(\mod 4)$ och $35 \equiv -1 \quad(\mod 4)$, så $n \equiv -l-1 \quad(\mod 4)$
• $315 \equiv 3\quad(\mod 8)$ och $35 \equiv 3 \quad(\mod 8)$, så $n \equiv 3l+3 \quad(\mod 8)$ 
• $315 \equiv 0 \quad(\mod 3)$, så $n \equiv 0l-1 \quad(\mod 3)\equiv -1\quad(\mod 3)$
• $315 \equiv 3 \quad(\mod 6)$, så $n \equiv 3l-1 \quad(\mod 6)$
• $315 \equiv 0 \quad(\mod 9)$, så så $n \equiv 0l-1 \quad(\mod 9)$

 

Av allt detta fick man tre krav på $l$:

• $-l-1 \equiv 1 \quad (\mod 4) \iff l \equiv 2 \quad(\mod 4)$, 
• $3l+3 \equiv 1 \quad (\mod 8) \iff 3l \equiv -2\quad(\mod 8) \iff l \equiv 2\quad(\mod 8)$
• $3l-1 \equiv -1 \quad (\mod 6) \iff 3l \equiv 0\quad(\mod 6) \iff l$ är jämnt

Totalt är $l=8j + 2$ där $j$ är ett naturligt tal. När detta sätts in i formeln för $n$, så får man att

$n = 315l+35 = 315(8j + 2) + 35 = 2520j + 665$.

Här ser man direkt att $j=0$ önskas för att hamna i rätt intervall

Tack! Däremot känns detta väldigt komplicerat. Hade nog aldrig själv kommit fram till det.