1. ## Modulo problem

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.

2. 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

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)

4. 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)$

5. Originally Posted by clockingly

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$)

6. 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.