dividing remainder w/exponents

Printable View

November 6th 2008, 12:57 PM
cassiopeia1289

dividing remainder w/exponents

For n is greater than or equal to 1, use congruence theory to find remainder of:

$7 | 5^(2n) + (3)(2^(5n-2))$

so here's what I did - I'm new to mod(s) so I wanted to make sure it goes right:

so:
$= (5^2)^n + (3)(2^{5n})(2^{-2})$
$= (25)^n + (3)(2^5)^n (2^{-2})$

$\equiv 4^n + (-4)(4)^n (2^{-2})$ (mod 7)
$\equiv 4^n + (-1)(4^n)$ (mod 7)
$\equiv 4^n (1 + -1)$ (mod 7)
$\equiv 0$ (mod 7)

yes??? does it work?
November 6th 2008, 01:46 PM
Laurent

Quote:

Originally Posted by cassiopeia1289

For n is greater than or equal to 1, use congruence theory to find remainder of:

$7 | 5^{2n} + (3)(2^{5n-2})$

so here's what I did - I'm new to mod(s) so I wanted to make sure it goes right:

so:
$= (5^2)^n + (3)(2^{5n})(2^{-2})$
$= (25)^n + (3)(2^5)^n (2^{-2})$

$\equiv 4^n + (-4)(4)^n (2^{-2})$ (mod 7)
$\equiv 4^n + (-1)(4^n)$ (mod 7)
$\equiv 4^n (1 + -1)$ (mod 7)
$\equiv 0$ (mod 7)

yes??? does it work?

This works, if you know what you meant when you wrote $2^{-2}$ . This does not mean 0.25 of course, but it refers to the inverse modulo 7, which is well defined since 2 and 7 are relatively prime. By the way, $2^{-1}=4\,({\rm mod}\, 7)$ .

If what you've just read does not make sense for you (which wouldn't be surprising if you're new to "moduli"), you should avoid writing negative powers. For instance, you can notice that $2^3\equiv 1\,({\rm mod}\,7)$ , hence $3\cdot 2^{5n-2}\equiv 2^3\cdot 3 \cdot 2^{5n-2}\equiv 3\cdot 2^{5n+1}\equiv 6 \cdot 2^{5n}\,({\rm mod}\,7)$ . And you can go on like you did.
November 6th 2008, 01:52 PM
cassiopeia1289

ok, but if before I turn it all into mod 7: $2^{-2}$ is equivalent to 1/4

so how is it that I didn't know what you just told me, and it can still be right?
November 6th 2008, 02:45 PM
Laurent

Quote:

Originally Posted by cassiopeia1289

ok, but if before I turn it all into mod 7: $2^{-2}$ is equivalent to 1/4

so how is it that I didn't know what you just told me, and it can still be right?

Using moduli only makes sense for integers. So that $\frac{1}{4}=0.25$ shouldn't be used with mod 7.

But in fact what you wrote is still right because $2^{-1}$ can be understood as an inverse with respect to the multiplication modulo 7 (and not with respect to the multiplication in $\mathbb{R}$ ). An inverse of $x$ modulo 7 is an integer $y$ such that $xy\equiv 1\,({\rm mod}\, 7)$ . This happens to exist for every $x$ which is not divisible by 7, and we denote it by $x^{-1}$ . The notation is the same as the notation for $\frac{1}{x}\in\mathbb{Q}$ but the "mod 7" prevents from any confusion.
Anyway, you'll soon learn about this in more details. For now, just be conscious that dividing is not straightforward when using moduli. You can add, multiply, but not always divide. Use the trick I said about $2^3\equiv 1$ to circumvent this problem elementarily.
November 6th 2008, 02:47 PM
cassiopeia1289

ok, thank you!