Talföljder 5

Vänta, vilken rest? Är det resten av (a + b)? 

Resten av a/b, sorry...

Ingen fara. Denna uppgift är lite lurig, faktiskt. 

Uttrycket kan skrivas om till multiplikation:

$\frac{a}{b}=a·\frac{1}{b}$

Det ser lite krångligare ut (eftersom vi inte vet vad 1/b blir, men bear with me on this one). En av modulolagarna ger att $(a·b) mod \left(n\right) \equiv (a (mod n\left)\right)·(b (mod n\left)\right)$. Det gör att vi kan skriva om vårt uttryck lite grann:

$(a (mod n\left)\right)·\left(\frac{1}{b} (mod n)\right)$.

Vi ska visa att om a och b är delbara med n är även produkten av uttrycket delbart med n. Om något är delbart med n har det resten noll, (mod n). Det innebär att $(a (mod n\left)\right)\equiv 0$. Om vi vill kan vi skriva a som $n·p$, där p är något annat heltal. Denna produkt är delbar med n, eftersom n ingår som faktor i talet. 

$$\begin{gathered} (a (mod n\left)\right)·\left(\frac{1}{b} (mod n)\right)\equiv 0 \\ 0·\left(\frac{1}{b} (mod n)\right)=0 \end{gathered}$$

Oavsett vad b är. QED.

Smutstvätt skrev :

Ingen fara. Denna uppgift är lite lurig, faktiskt. 

Uttrycket kan skrivas om till multiplikation:

$\frac{a}{b}=a·\frac{1}{b}$

Det ser lite krångligare ut (eftersom vi inte vet vad 1/b blir, men bear with me on this one). En av modulolagarna ger att $(a·b) mod \left(n\right) \equiv (a (mod n\left)\right)·(b (mod n\left)\right)$. Det gör att vi kan skriva om vårt uttryck lite grann:

$(a (mod n\left)\right)·\left(\frac{1}{b} (mod n)\right)$.

Vi ska visa att om a och b är delbara med n är även produkten av uttrycket delbart med n. Om något är delbart med n har det resten noll, (mod n). Det innebär att $(a (mod n\left)\right)\equiv 0$. Om vi vill kan vi skriva a som $n·p$, där p är något annat heltal. Denna produkt är delbar med n, eftersom n ingår som faktor i talet. 

$$\begin{gathered} (a (mod n\left)\right)·\left(\frac{1}{b} (mod n)\right)\equiv 0 \\ 0·\left(\frac{1}{b} (mod n)\right)=0 \end{gathered}$$

Oavsett vad b är. QED.

Jag tyckte att det såg ut mycket elegant ut. Men skulle inte detta uttryck vända sig emot oss och bita handen som skappade den, som en rabid hund?

$$\begin{gathered} \frac{a}{b}=a\times \frac{1}{b} \\ \left(a\right(modn\left)\right)\times \left(\frac{1}{b}\right(modn\left)\right) \end{gathered}$$

Men b är också noll när modulo delat med nl!

Och nu har vi $a*\frac{1}{0}!$

Eller är jag ute och simmar i skogen?

b kan inte vara noll från början, eftersom division med noll är förbjudet. Men hur menar du att "b är noll när modulo delat med n"? $\frac{1}{b} (mod n) =/= \frac{1}{b (mod n)}$. 

Smutstvätt skrev :

b kan inte vara noll från början, eftersom division med noll är förbjudet. Men hur menar du att "b är noll när modulo delat med n"? $\frac{1}{b} (mod n) =/= \frac{1}{b (mod n)}$. 

Jag menade, på samma sätt som a blir noll när delat med modulo n, blir b noll när delat med modulo n, och gör att vi har en division med noll.

Men om vi har $\frac{1}{12}$ (mod 12), det är inte 12 som delas med (mod 12) utan 0.0833... så nej, det var definitiv en skog promenad.

Ja, lite skogspromenad faktiskt. Problemet är att du antar att $\frac{a}{b}(mod n)=\frac{a (mod n)}{b (mod n)}$. Det stämmer inte.