# Division table modulo 5

• August 2nd 2009, 04:24 AM
MAX09
Division table modulo 5
Hi,

I was actually looking for some notes regarding the history of the Chinese Remainder theorem and came across the link

Chinese Remainder Theorem where they illustrate a solution which involves division table modulo 5. I quote the problem here,

p1: x = 2 (mod 3)
p2: x = 3 (mod 5)
p3: x = 2 (mod 7)

From p1, x = 3t + 2, for some integer t. Substituting this into p2 gives 3t = 1 (mod 5).
Looking up 1/3 in the division table modulo 5, this reduces to a simpler equation

p4: t = 2 (mod 5)
I'm not able to follow how the '1/3' gives way to t = 2 mod 5. I tried looking for the division table modulo 5 in the web but couldn't find anything substantial.

Can anyone shed some more light on this table?

Thanks,
Max
• August 2nd 2009, 05:28 AM
flyingsquirrel
Hi,
Quote:

Originally Posted by MAX09
From p1, x = 3t + 2, for some integer t. Substituting this into p2 gives 3t = 1 (mod 5).
Looking up 1/3 in the division table modulo 5, this reduces to a simpler equation

p4: t = 2 (mod 5)
I'm not able to follow how the '1/3' gives way to t = 2 mod 5. I tried looking for the division table modulo 5 in the web but couldn't find anything substantial.

'1/3' denotes an inverse of 3 modulo 5, that is to say a number $n$ such that $n\times 3\equiv 1 \pmod{5}$. As $2\times 3=6\equiv 1\pmod{5}$, 2 is an inverse of 3 modulo 5. Now if we multiply both sides of
$3\times t \equiv 1 \pmod{5}$
by 2 we get
$2\times3\times t \equiv 2 \pmod{5}$
that is to say
$t \equiv 2 \pmod{5}$
since $2\times 3\equiv 1\pmod{5}$.