Visa att

Pröva att sätta in några exempel på x, y, n och c och se så att det stämmer och sedan logiskt tänka efter om det stämmer och (eftersom uppgiften säger att det stämmer) sedan logiskt tänka efter varför det stämmer för generella värden på x, y, n och c.

Jo men jag kommer inte fram till varför de stämmer 

Ja att visa det är inte så enkelt. Ett försök kommer här:

Om $cx\equiv cy$i mod n så gäller att $\frac{cx}{n}=k_1+r$där k₁ = kvot 1 och r = rest och $\frac{cy}{n}=k_2+r$

Vi löser ut c ur bägge ekvationerna och får $c=\frac{n(k_1+r)}{x}$samt $c=\frac{n(k_2+r)}{y}$

Vi sätter de två lika med varandra $\frac{n(k_1+r)}{x}=\frac{n(k_2+r)}{y}$och med lite omstuvning

$\frac{x}{y}=\frac{n(k_1+r)}{n(k_2+r)}$och vi har $\frac{x}{n}=k_1+r$och $\frac{y}{n}=k_2+r$vilket visar att $x\equiv y$

Jag känner mig inte helt övertygad själv, men kanske någon vänlig själ vill kommentera det?

Få se nu. Jag använder ett specifikt exempel för att tänka.

x är 171, n är 10, y är 21, c är 15.

cx är då 170*15+1*15; den första termen är det som går jämnt ut då man dividerar med 10 den andra är restvärdet gånger 15.

cy är 20*15+1*15, samma uppdelning som ovan.

den första termen i båda talen går jämnt ut då man delar med n så den påverkar ej modulo värdet; den andra termen är det ända som kan påverka. Eftersom resttermen var samma för x och y (då deras modulo värde var samma) måste den termen vara ett och samma värde multiplicerat med c, vilket gör att cx måste ge samma rest som cy. Och detta var det som skulle visas.

Tog du bara random siffror eller har du räknat ut dem?

Jag tog n som 10 för att det är enkelt att räkna med och sedan tog jag bara två tal på slump som ger samma rest då man delar med 10 (=de har samma ental).

I varje fall, om man generaliserar så kommer x och y kunna delas upp i två delar, en som är en multipel av n och en som är ett tal mindre än n, dvs. resttalet. Multiplicerar man sedan x och y med c kommer delen som är en multipel av n fortfarande vara en multipel av n efter att man multiplicerat med c, så det påverkar inte modulo-talet. Endast delen som är resttalet kan påverka, och det kommer bli resttalet gånger c för båda talen. Och om de x och y hade samma modulovärde så är resttalet samma, så vi har effektivt ett och samma tal, så de måste vara samma.

Är detta ett korrekt svar på frågan? :)

Som sagt var mitt exempel bara för att tänka. Vill man faktiskt bevisa bör man skriva något i stil med "då man delar x och y med n kommer man få en del som utgör en multipel av n och en del som är resttermen. Ansätt detta till x= k_x+r_x och y= k_y + r_y. Multiplicerar man detta med c så kommer k_x och k_y fortfarande vara en multipel av n så de påverkar ej modulo-värdet" och sedan det resonemang som jag förde i slutet på inlägg #7.

Jag är också lite tveksam till ConnyN's lösning. Om vi bara antar att cx är till exempel 171 och n är 10 så kommer vi få att det står

$\frac{171}{10}=17+1$

Vi har då skrivit att 17,1=18 vilket inte stämmer. Man borde skriva

$\frac{171}{10}=17 rest 1$

Vill man sedan multiplicera båda leden med n så bör resttermen ej multipliceras eftersom det är en term som aldrig har dividerats med n, och vid det laget ifrågasätter jag om resonemanget håller.

Bedinsis skrev:

Jag är också lite tveksam till ConnyN's lösning. Om vi bara antar att cx är till exempel 171 och n är 10 så kommer vi få att det står

$\frac{171}{10}=17+1$

Vi har då skrivit att 17,1=18 vilket inte stämmer. Man borde skriva

$\frac{171}{10}=17 rest 1$

Vill man sedan multiplicera båda leden med n så bör resttermen ej multipliceras eftersom det är en term som aldrig har dividerats med n, och vid det laget ifrågasätter jag om resonemanget håller.

Helt rätt. Jag blandade ihop saker och ting. Precis som Bedinis så började jag med ett exempel och såg att det gick bra. Därifrån till att skriva ihop något som gäller generellt så gjorde jag galet. Det är inte helt lätt eftersom det är mycket enkelt om man får använda reglerna för kongruens, men ska man bevisa en sådan regel så är det inte fullt så enkelt. 

En länk som förklarar rätt bra är denna. Jag hinner inte riktigt att fördjupa mig i det idag, men det kanske kan vara ett tips? Även det Benedis skriver kan säkert utvecklas till något mer generellt gällande bevis.

Tillägg: 16 apr 2023 10:48

Ursäkta Bedinsis ska det vara

Nu har jag tittat på länken som jag tyckte var mycket bra och studerat vad Bedinsis skrivit och gör ett nytt försök.

Vi har ett heltal $k_x$så att $x=k_x·n+r$och ett heltal $k_y$så att $y=k_y·n+r$
Eftersom $x\equiv y (mod n)$så har de samma rest $r$

Om vi nu multiplicerar x och y med c så får vi $cx=c{k}_x·n+cr$och $cy=c{k}_y·n+cr$

Vad vi ser av det är att $c{k}_x och c{k}_y$är två nya konstanter och $cr$är en annan.

Vi kan skriva dem som $cx=k_{cx}·n+r_c$och $cy=k_{cy}·n+r_c$bägge i (mode n).

OBS! att $r_c$är gemensam för $cx$ och $cy$eftersom vi multiplicerade r med c för både $cx$och $cy$.

Eftersom de har samma rest så gäller att $cx\equiv cy (mod n)$