Tag archieven: chinese reststelling

Opgave 19

Geplaatst op door

Controleer voor elk natuurlijk getal vanaf 7 of {n} \choose {7} deelbaar is door 12 en bereken de fractie van dergelijke getallen. Zoek de limiet van die fractie als je steeds meer getallen controleert.

Antwoord
  • We weten dat {n} \choose {7} = \dfrac{n!}{7!(n-7)!}=\dfrac{n(n-1)\cdots(n-6)}{2^4.3^2.5.7}
  • Om deelbaar te zijn door 12 moet de teller deelbaar zijn door {2^6.3^3.5.7}. Omdat de teller betsaat uit zeven opeenvolgende getallen is die zeker al deelbaar door 7 en 5.
  • Bekijken we nu de factoren 3. De teller is zeker deelbaar door 9, want zeven opeenvolgende getallen bevatten zeker twee veelvouden van 3.
  • Als n \equiv 0,1,2,3,4,5 \text{ of } 6 \text{ mod } 9, dan is zeker één van de zeven getallen uit de teller deelbaar door 9 en een ander door 3, zodat de teller deelbaar is door 3^3.
  • Nu de factoren 2: Als n even is dan zijn n,n-2,n-4 en n-6 allemaal deelbaar door 2 en juist twee getallen zijn een viervoud, zodat de teller dan deelbaar is door 2^6.
  • Als n oneven is dan zijn n-1,n-3 en n-5 deelbaar door 2. Als n-3 het enige getal is dat deelbaar is door 4, dan moet het zelfs deelbaar zijn door 16 anders kan de teller niet deelbaar zijn door 2^6. Dus moet n \equiv 3 \text{ mod } 16. Als n-1 en n-5 beiden deelbaar zijn door 4, dan moet opdat de teller  deelbaar zou  zijn door 2^6, een van die getallen deelbaar zijn door 8. Dus moet n \equiv 1,5 \text{ mod } 8 of n \equiv 1,5,9,13 \text{ mod } 16.
  • Brengen we nu alle informatie samen: {n} \choose {7} is deelbaar door 12 als en slechts als

        \[\begin{cases} n \equiv 0,1,2,3,4,5,6 \text{ mod } 9 \\ n \equiv 0,1,2,3,4,5,6 ,8,9,10,12,13,14 \text{ mod } 16\]

  • Er zijn 7 mogelijkheden modulo 9 en 13 mogelijkheden modulo 16, dus zijn er volgens de Chinese reststelling 9.13=91  oplossingen modulo 9.16=144.
  • De waarschijnlijkheid dat {n} \choose {7}  deelbaar is door 12 nadert dus de waarde \frac{91}{144}.

Opgave 18

Geplaatst op door

n \in \mathbb{N}_0 is p-veilig ( met p een natuurlijk getal verschillend van 0), als het in absolute waarde meer dan 2 verschilt van alle p-vouden. Hoeveel natuurlijke getallen bestaan er die kleiner zijn dan 10000 en tegelijkertijd 7- veilig, 11-veilig en 13-veilig zijn?

Antwoord

  • Even op onderzoek: welke zijn de 10-veilige getallen? Het zijn: 3,4,5,6,7,13,14,15,16,17,23,…
  • als x zowel 7-veilig, 11-veilig en 13-veilig moet zijn dan geldt
    \begin{cases} x\equiv 3,4 \text{ mod } 7 \\ x\equiv 3,4,5,6,7,8 \text{ mod } 11 \\ x\equiv 3,4,5,6,7,8,9,10 \text{ mod } 13 \end{cases}
  • Eigenlijk staan hier 2.6.8=96 stelsels die , volgens de chinese reststelling, allemaal een unieke oplossing hebben modulo 7.11.13=1001
  • Tussen 1 en 1001 hebben we dus 96 oplossingen, idem tussen 1002 en 2002, tussen 2003 en 3003, …, tussen 9009 en 10010. Bijgevolg hebben we 10.96 = 960 oplossingen.
  • Maar misschien zijn er wel oplossingen bij die  groter zijn dan 10000, vermits we tot 10010 gerekend hebben. We controleren en vinden dat 10006 \equiv -4 \text{ mod } 1001 en dus bij deling door 7,11 en 13 respectievelijk 3,7,en 9 als rest laat. Zodoende is 10006 zowel 7-veilig als 11-veilig en 13-veilig. Het zelfde geldt voor 10007 \equiv -3 \text{ mod } 1001.
  • Bijgevolg zijn er 960 – 2= 958 getallen die zowel 7-veilig, 11-veilig als 13-veilig zijn.

De Chinese reststelling

Geplaatst op door

Naast lineaire congruenties , kan je ook werken met stelsels van lineaire congruenties. Zoals bijvoorbeeld:

Volgens de Chinese reststelling geldt dan: Als elke a_i en m_i onderling ondeelbaar zijn en als alle m_i twee aan twee onderling ondeelbaar zijn, dan heeft dit stelsel een unieke oplossing modulo m_1.m_2.\cdots.m_n.

Los op:
\begin{cases} x\equiv 2 \text{ mod }5 \\3x\equiv 1 \text{ mod }8 \end{cases} of  \begin{cases} x\equiv 2 \text{ mod }5 \\x\equiv 3 \text{ mod }8 \end{cases}

Dit betekent dat x=2+5k=3+8l. Dus 5k \equiv 1 \text{ mod } 8 of k \equiv 5 \text{ mod } 8. Hieruit volgt dat k=5+8p en dus is x=2+5(5+8p)=27+40p.

De unieke oplossing van het gegeven stelsel is x=27 \text{ mod } 40.