Kongruenser - bevis

Hej!

Uppgift:

a) Låt $a$ vara ett jämnt heltal. Bevisa att $a^{2} \equiv 0 m o d 4$ .

b) Låt $a$ vara ett udda heltal. Bevisa att $a^{2} \equiv 1 m o d 8$ . Härled att $a^{2} \equiv 1 m o d 4$ .

c) Bevisa att om $n$ är ett positivt heltal sådan att $n \equiv 3 m o d 4$ så kan inte $n$ skrivas som summan av två heltal i kvadrat ( $n \neq a^{2} + b^{2}, a, b \in ℤ$ ).

d) Bevisa eller motbevisa det motsatta förhållandet till påståendet i c) ovan.

Lösning:

a) $a^{2} \equiv 0 m o d 4 \Leftrightarrow 4 | a^{2}$

Eftersom $a$ är jämn så är $a = 2 x \Rightarrow a^{2} = 4 x^{2}$ för något heltal $x$ . Så

$4 | 4 x^{2} \Leftrightarrow 4 | a^{2} \Leftrightarrow a^{2} \equiv 0 m o d 4$ .

b) $a^{2} \equiv 1 m o d 8 \Leftrightarrow 8 | a^{2} - 1$

Eftersom $a$ är udda så är $a + 1 = 2 x \Leftrightarrow a = 2 x - 1 \Rightarrow a^{2} = (2 x - 1)^{2} = 4 x^{2} - 4 x + 1$ för något heltal $x$ .

$a^{2} - 1 = 4 (x^{2} - x) \Rightarrow 4 | a^{2} - 1 \Leftrightarrow a^{2} \equiv 1 m o d 4$ . Detta är samma sak som att skriva

$a^{2} = 4 k_{0} + 1$ för något heltal $k_{0}$ . Låt $k_{0} = 2 k_{1}$ där $k_{1}$ är ett heltal. Då är $a^{2} = 4 k_{0} + 1 = 8 k_{1} + 1 \Leftrightarrow a^{2} \equiv 1 m o d 8$ .

c) Här får jag inte till det. I "facit" står en ledtråd som lyder:

Antag att $n$ kan skrivas som summan av kvadraten av två heltal och härled en motsägelse genom att titta på ekvationen modulo 4 och genom att använda delarna a) och b).

d) -

Det ser lite konstigt ut på b), jag vet inte riktigt hur du motiverar att $k_0 = 2k_1$ ? Jag skulle sen också bara försöka hålla mig till modulär aritmetik.

a) a = 2n för något heltal n, vilket innebär att $a^{2} \equiv (2 n)^{2} \equiv 4 n^{2} \equiv 0 (m o d 4)$ .

b) a = 2n + 1 för något heltal n, vilket innebär att $a^{2} \equiv (2 n + 1)^{2} \equiv 4 n^{2} + 4 n + 1 \equiv 4 n (n + 1) + 1 (m o d 8)$

Nu måste n(n + 1) vara jämnt, därför är 4n(n + 1) delbart med 8, vilket alltså ger att

$a^{2} \equiv 4 n (n + 1) + 1 \equiv 1 (m o d 8)$

Eftersom ^2 = 8k + 1 så får man omedelbart att a^2 = 1 (mod 4). En fördel med att se det i modulär aritmetik är att man kan göra beviset så här också

$1^{2} \equiv 1 (m o d 8) 3^{2} \equiv 1 (m o d 8) 5^{2} \equiv 1 (m o d 8) 7^{2} \equiv 1 (m o d 8)$

Vilket är tillräckligt för att visa att a^2 = 1 (mod 8) då a är udda.

c) Säg att $n = a^2 + b^2$ vilka värden kan då $n (mod 4)$ ha? Från a) och b) så får du vad $a^2$ och $b^2$ kan anta för värden mod 4, så gå igenom alla de tänkbara värdena och se vad n får för värden mod 4.

d) Skulle du kunna formulera det som det frågas efter i egna ord?

Svara