Kongruens / Inkongruens

Kongruenta    ...$\equiv$
Inkongruenta ...$\not\equiv$
Då menar du väl:
$10x\not\equiv 500 (mod 3)$

Annars rekommenderar jag t.ex.:
https://sv.wikipedia.org/wiki/Modul%C3%A4r_aritmetik

Kort och gott så blir ju ekvationen

$ax \equiv b (mod n)$

Den samma som att lösa den diofantiska ekvationen

$ax + ny =\hspace{0.17em}b$

Så för att det över huvud taget ska existera en lösning, så vet vi att det måste gälla att gcd(a, n) | b. Om så är fallet vet vi att det existerar åtminstone en lösning, kalla den för $x_0, y_0$. Vi vet då att vi får alla lösningar av

$$\begin{gathered} x =\hspace{0.17em}{x}_0+\frac{n}{gcd(a, n)}k \\ y =\hspace{0.17em}{y}_0-\frac{a}{gcd(a, n)}k \end{gathered}$$

Så man kan se att vi kommer ha gcd(a, n) inkongruenta mod n stycken lösningar till denna ekvation.

Inkongruens, de som inte har samma rest vid heltalsdivision, eller hur?

Men jag förstår fortfarande inte hur "man" kan se att man har n  antal inkongruenta lösningar inom ett angivet intervall. När man räknar inkongruens mod n så letar man väl efter alla inkongruenta lösningar $0 \le x <n$?

Ja de som är inte får samma rest vid heltalsdivision är inkongurenta.

Du får att dom blir kongruenta om man kan lägga på någon multipel av n. Exempelvis a och a + 4n kommer vara kongruenta mod n. Men lägger jag på något som är mindre än n så kommer man ju få att dom blir inkongruenta.

I detta fall så har vi ju att lösningarna är

$x =\hspace{0.17em}{x}_0+\frac{n}{gcd(a, n)}k$

vi kommer ju först att lagt på n då vi valt k som gcd(a, n). Så de inkongruenta lösningarna är

$$\begin{gathered} x_1=x_0 \\ {x}_2=x_0+\frac{n}{gcd(a, n)} \\ {x}_3=x_0+\frac{2n}{gcd(a, n)} \\ {x}_4=x_0+\frac{3n}{gcd(a, n)} \\ ⋮ \\ {x}_{gcd(a, n)}=x_0+\frac{\left(gcd\right(a, n)\hspace{0.17em}- 1)n}{gcd(a, n)} \end{gathered}$$

Tar vi någon annan lösning så kan vi få någon av dessa genom att lägga på/dra bort någon multipel av n.

Jag förstår fortfarande inte... Jag trodde jag gjorde. Men säg att man har en ekvation där, efter att man uttryckt gcdn som en linjärkombination och förlängt för att matcha HL i ekvationen. Då kanske man sitter med ett X-värde på 100.000. Och jag ska räkna i mod 75. Ska jag hitta samtliga lösningar, mha din ekvation, i 0-74?

För övrigt så tror jag du menar att $ax\equiv b (mod n)\iff ax= b + ny\iff ax-ny=b$? Det står så i min bok iaf. 

Jag vet inte riktigt om jag är med på hur du menar, har du något konkret exempel?

Det är egentligen inte någon väsentlig skillnad på ekvationen ax + ny = b och ekvationen ax - ny = b, jag var medveten om att man får ett minus om man skriver på sättet du gjorde, men valde att skriva plus efter ekvationen blir lite snyggare. Anledningen till att det inte spelar någon roll är att man kan ersätta y med -y och det påverkar ingenting för resonemanget.

$$\begin{gathered} 561x\equiv 3575 (mod 1562) \iff 561x+1562y =\hspace{0.17em}3575 \\ gcd(1562, 561)\hspace{0.17em}=\hspace{0.17em}11 \end{gathered}$$

Enligt dig ska alltså ekvationen ovan ha 11 inkongruenta lösningar.

Det är nästa steg jag inte förstår. Ska jag ställa gcdn som en linjärekvation och sedan köra din formel ovan för att hitta de värden som ligger inom angivet intervall (0 - 1561)?

Ja alltså du behöver börja med att finna en partikulärlösning till ekvationen. Jag gissar på att du vet hur man gör det? Så jag drar bara fram dom och säger att x = 37, y = -11 är en partikulärlösning till ekvationen. Nu får man alltså alla lösningar av

$x =\hspace{0.17em}37 + \frac{1562}{11}k=37+142k$

Så lösningarna är

x = 37,

x = 37 + 142 = 179

x = 37 + 142*2 = 321

x = 37 + 142*3 = 463

...

x = 37 + 142*10 = 1457

Nu kan du exempelvis verifiera att om vi har att

$37 + 142*11 \equiv 1599 \equiv 37 (mod 1562)$

Så skulle vi fortsätta leta lösningar så börjar dom så att säga bara om och dem blir bara kongruenta mot de vi redan hittat.

Notera också att det är bra att börja med att förenkla ekvationen eftersom du har att 3575 = 451 (mod 1562)

Hade inte räknat med partikulärlösningar tidigare. Men jag tittade exempel (som jag förstod lite halvt) och kom fram till att jag hade fått samma svar tidigare idag (på annat vis) bara att jag inte visste om att de var inkongruenta.

Jag uttryckte gcdn som en linjärkombination med hjälp av lcm och sedan undersökte vilka värden på X som låg i ${\mathrm{\mathbb{Z}}}_n$

Det blir alltså samma resultat bara en mycket längre väg (som det ser ut som?)

Ja alltså partiklärlösningarna kommer man ju fram till genom att "uttrycka gcd som en linjär kombination". Men sedan hur du gjorde med lcm vet jag inte riktigt, jag är nog inte bekant med det sättet.

Men är du med på hur sättet jag visade fungerar?

Ja, jag är med på det. :) Tack!

$$\begin{gathered} ax + by = z \\ lcm =\hspace{0.17em}\left\{\begin{array}{l}\frac{a}{gcd(a,b)}*b\\ \frac{b}{gcd(a,b)}*a\end{array}\right. \end{gathered}$$

Två varianter av det, sen faktoriserar jag in det i det ursprungliga: 
$$\begin{gathered} (x+\frac{b}{gcd(a,b)}k)*a \\ (y+\frac{a}{gcd(a,b)}k)*b \\ k \in \mathrm{\mathbb{Z}} \end{gathered}$$

Sen stegade jag helt enkelt ner X-värdet till det att jag hamnade inom rätt intervall.

Jag är jävligt trött så det kan vara helt tokigt. (sen är jag oerhört dålig på att skriva matematiska formler, men två negativa..?)

Hmm, vet inte om jag är helt med på hur du menar. Men jag kan lägga till att det är ju inte säkert att man finner det minsta positiva x som partikulärlösning. Man skulle ju i exemplet du gav istället funnit x = 179. Men då hade man bara kunnat låta

x = 179,

x = 321,

x = 463,

...

..

x = 179 + 142*10 = 1599 = 37 (mod 1562)

Så om man får en för stor lösning så kan man bara dra bort 1562 från den. Hittar man alltså en partikulärlösning kan man bara köra på från den och sedan dra bort från de lösningar man hittar.

Nu har jag dock förstått vad som menas och för det tackar jag!