Modulo problem

**clockingly** · November 29th 2006, 03:55 PM

Okay, so I'm supposed to find the least nonnegative integer i such that

4^30 is congruent to i (mod 19).

I'm not sure how to approach this since my textbook doesn't really say how this type of problem is done so any help would be greatly appreciated.

**topsquark** · November 29th 2006, 04:10 PM

Originally Posted by clockingly

Okay, so I'm supposed to find the least nonnegative integer i such that

4^30 is congruent to i (mod 19).

I'm not sure how to approach this since my textbook doesn't really say how this type of problem is done so any help would be greatly appreciated.

My approach here won't be unique, but the method should be fairly clear.

$4^3 = 64 \equiv 7$ (mod 19)

So
$4^{30} = (4^3)^{10} \equiv 7^{10}$ (mod 19)

Again:
$7^2 \equiv 11$ (mod 19)

So
$7^{10} = (7^2)^{5} \equiv 11^5$ (mod 19)

You can probably do this one by directly but we can simplify this one last time:
$11^2 \equiv 7$ (mod 19)
$11^3 \equiv 1$ (mod 19)

So finally:
$4^{30} \equiv 7^{10} \equiv 11^5 = 11^2 \cdot 11^3 \equiv 7 \cdot 1 = 7$ (mod 19)

$4^{30} \equiv 7$ (mod 19)

-Dan

**clockingly** · November 29th 2006, 04:28 PM

Thanks for your help.

I am still a little confused as to how you got the very first equation though (listd below)...I'm a little confused as to where the 7 came from...

4^3 = 64 is congruent to 7(mod 19)

**ThePerfectHacker** · November 29th 2006, 04:33 PM

Originally Posted by clockingly

Okay, so I'm supposed to find the least nonnegative integer i such that

4^30 is congruent to i (mod 19).

I'm not sure how to approach this since my textbook doesn't really say how this type of problem is done so any help would be greatly appreciated.

You can also do this...
$4^{30}=2^{60}$
And,
$2^{18}\equiv 1 (\mbox{ mod }19)$
By Fermat's little theorem since 19 is prime not divisible by 2.
Cubing,
$2^{54}\equiv 1 (\mbox{ mod }19)$
Multiply both sides by $2^6=64\equiv 7$ we we have,
$2^{60}\equiv 7 (\mbox{ mod }19)$

**ThePerfectHacker** · November 29th 2006, 04:34 PM

Originally Posted by clockingly

Thanks for your help.

I am still a little confused as to how you got the very first equation though (listd below)...I'm a little confused as to where the 7 came from...

4^3 = 64 is congruent to 7(mod 19)

That is becuase,
$64\equiv 7 (\mbox{ mod }19)$
Right?

Because it leaves a remainder of 19.

( $64=3\cdot 19+7$ )

**Soroban** · November 29th 2006, 09:03 PM

Hello, clockingly!

Another approach . . .

Find the least nonnegative integer $n$ such that: . $4^{30} \equiv n \pmod{19}$

I found that: . $4^5 \:=\:1024 \:\equiv\:-2 \pmod{19}$

Then: . $4^{30} \:=\:(4^5)^6 \:\equiv\:(-2)^6 \pmod{19}$

And: . $(-2)^6\:=\:64\:\equiv\:7\pmod{19}$

Therefore: . $4^{30}\:\equiv\:7\pmod{19}$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

I also found that: . $4^9\:\equiv\:1\pmod{19}$

Then: . $4^{30}\:=\:\left(4^9\right)^3\cdot4^3 \:\equiv\:(1^3)4^3\pmod{19}$

And: . $4^3\:=\:64\:\equiv\:7\pmod{19}$

But I see that TPHacker beat me to it.

Thread: Modulo problem

LinkBack

Thread Tools

Display

Modulo problem

Similar Math Help Forum Discussions

Modulo problem

Modulo problem

Modulo of squares = modulo of roots

Help with Modulo Problem

Modulo problem

Search Tags