kongruens modulo oppgave

[hallapaadeg]

Har denne oppgaven

"Let m be an integer such that $m \geq 2$. Consider the statement"

$(*)$ For all integers $a$ and $b$, if $ab \equiv 0 \ (\text{mod } m)$, then $a \equiv 0 \ (\text{mod } m)$ or $b \equiv 0 \ (\text{mod } m)$

a) Show that $(*)$ is true if m is a prime number.

b) Show that $(*)$ is not true when m is NOT a prime.

Jeg har ikke kommet så langt på denne. Har på følelsen at det er ganske lett å vise, men det er ikke klart for meg.

Vet at hvis $ab \equiv 0 \ (\text{mod } m)$, betyr det at $m \ \vert \ ab - 0$. Altså $ab = mk$ for et ukjent heltall k

Men hva har det å si at m er et primtall eller ikke? Antar det har noe med faktoriseringen av tallet å gjøre. Men vet ikke hvordan jeg skal vise det. Noen som har noen tips?

[Gustav]

a) Hvis m er primtall, eksisterer det inverser for alle elementene forskjellig fra 0, modulo m. Betrakt $ab\equiv 0 \mod m$. Dersom $a\not \equiv 0$, så vil $a^{-1}ab\equiv a^{-1}0\equiv 0$, så $b\equiv 0$.

b) Hvis m er sammensatt, fins p og q slik at $m=pq$, og $p,q\neq 1$. Dermed må p,q<m, så $pq\equiv 0$, $p\not\equiv 0$, $q\not\equiv 0$, $\mod m$