Modular arithmetic congruence class simple proof

Question

I have the following question but I'm unsure of how it can be approached by a method of proof. I'm new to modular arithmetic and any information on how to solve this would be great for me.

(b) Let $t,s\in\{0,1,2,3,4,5\}$. In $\mathbb Z_{25}$, prove that $[t]\,[s]\neq[24]$.

score 1 · Answer 1 · answered Oct 08 '12 at 15:18

1

Imagine trying everything. Clearly $5\cdot 5$ is no good. All the other choices give (ordinary) product $m$ between $0$ and $20$, so it is clear that $25$ cannot divide $24-m$.

answered Oct 08 '12 at 15:18

André Nicolas

507,029

score 0 · Answer 2 · answered Oct 08 '12 at 15:14

0

First note that $24\equiv -1\pmod{25}$ and hence we are trying to show that $ts\not\equiv-1\pmod{25}$. Suppose for contradiction that $ts\equiv -1\pmod{25}$, then multiplying through by $-1$ we get $-ts\equiv 1\pmod{25}$ so $t$ or $s$ is invertible, say $t$ with inverse $-s$. Therefore $\gcd(t,25) = 1$ (why?), and hence $t = 1,2,3,4$. There is a unique value of $s$ corresponding to each of these (why?), each of which should give you a contradiction.

answered Oct 08 '12 at 15:14

John Martin

1,229
8
17

very nice, well put ! im still getting my head around it though so this might take me a while – Daniel Del Core Oct 08 '12 at 15:22
so is [t] [s] just any values within the set? – Daniel Del Core Oct 08 '12 at 15:26
$[t][s]$ refers to the product of the equivalence classes of $[t]$ and $[s]$ taken modulo $25$ – John Martin Oct 08 '12 at 15:32

score 0 · Answer 3 · answered Oct 08 '12 at 15:28

Hint $\ $ If $\rm\:a\:|\:b\:$ in $\Bbb Z$ then so too in every ring, and the quotient is unique if $\rm\:a\:$ is not a zero divisor. Also, divisors of units are units, so $\rm\: mod\ 25\:$ the divisors of $\:24\equiv -1\:$ are units, so coprime to $5$.

Modular arithmetic congruence class simple proof

3 Answers3