# Modular arithmetic

• Nov 18th 2008, 03:07 PM
posix_memalign
Modular arithmetic
How do I solve:

tr^(-a) ≡ m (mod p)

where:

t = 6
r = 7
a = 6
p = 17

6*7^(-6) ≡ 0.000050999 (mod 17)

This obviously isn't right?

Edit: Sorry, I typed t = 7, it should have been t = 6, now corrected, and the -a should be ^(-a) due to a copy-paste which I neglected to check if copied itself correctly, apparently it did not, sigh.
• Nov 18th 2008, 04:35 PM
o_O
$\begin{array}{rcll} {\color{red}t}{\color{blue}r} - {\color{magenta}a} & \equiv & m & (\text{mod } {\color [cmyk] {0,.35,1,0}p}) \\ {\color{red}(7)}{\color{blue}(7)} - {\color{magenta}(6)} & \equiv & m & (\text{mod } {\color [cmyk] {0,.35,1,0}17}) \\ 43 & \equiv & m & (\text{mod }17) \end{array}$

You accidentally plugged in 6 instead of 7 for $t$.

Now that last line is essentially asking: "What is the remainder after 43 is divided by 17?"
• Nov 18th 2008, 04:45 PM
posix_memalign
Quote:

Originally Posted by o_O
$\begin{array}{rcll} {\color{red}t}{\color{blue}r} - {\color{magenta}a} & \equiv & m & (\text{mod } {\color [cmyk] {0,.35,1,0}p}) \\ {\color{red}(7)}{\color{blue}(7)} - {\color{magenta}(6)} & \equiv & m & (\text{mod } {\color [cmyk] {0,.35,1,0}17}) \\ 43 & \equiv & m & (\text{mod }17) \end{array}$

You accidentally plugged in 6 instead of 7 for $t$.

Now that last line is essentially asking: "What is the remainder after 43 is divided by 17?"

Thanks but I'm sorry I copy pasted the problem from Openoffice where I was working on it and thus some formatting was changed, I also managed to enter a typo from the part I didn't copy and paste -- incredible -- however, now it should be correct.
• Nov 18th 2008, 05:01 PM
o_O
$\begin{array}{rcll} tr^{-a} & \equiv & m & (\text{mod } p) \\ (6)(7)^{-6} & \equiv & m & (\text{mod } 17) \\ 6 \cdot \displaystyle \frac{1}{7^6} & \equiv & m & (\text{mod } 17) \\ 6 & \equiv & 7^6m & (\text{mod } 17) \end{array}$

One can show that: $7^6 \equiv 9 \ (\text{mod } 17)$...and... $6 \equiv -45 \ (\text{mod }17)$

So that last line becomes: $-45 \equiv 9m \ (\text{mod } 17)$