Congruence Problem

harkapobi · #1 $Old$ November 18th, 2009, 10:17 AM

Hi, I need to solve this congruence.

$7^x \equiv 6 (mod17)$

In the question, it has a squiggly line at the top of the congruence sign, but i'm not sure what that means

.

I know this questions probably has something to do with primitive roots, but I really dont know how to start.

Please help.
Katy

qmech · #2 $Old$ November 18th, 2009, 10:38 AM

Just multiply. Listing the powers of 7 mod 17 gives:
$7^1 \equiv 7 (mod 17)$
$7^2 = 7*7 = 49 \equiv 15 (mod 17)$
$7^3 \equiv 7*15 \equiv 3 (mod 17)$
etc. If my remainders are correct, the list of remainders with increasing powers of 7 are:
7,15,3,4,11,9,12,16,10,2,14,13,6,...,
so
$7 ^ {13} \equiv 6 (mod 17)$

harkapobi · #3 $Old$ November 18th, 2009, 10:49 AM

Ahh ok cool. Thank you

Is this the only way of solving this congruence? What if x was really large? this could take a long time.

And do you know what the wiggley line means at the top of the congruence sign? I didn't know how to write it in the math code. lol.

qmech · #4 $Old$ November 18th, 2009, 11:01 AM

A congruence sign is often written as an equals sign with a wiggly line on top of it. Another way is the 3 line equal sign you see here.

Yes, if x is large it could take a long time. However this is very simple to program onto a computer.

There are some shortcuts. For example, writing
$15 \equiv {-2} (mod 17)$
keeps the numbers smaller.

aidan · #5 $Old$ November 18th, 2009, 11:44 AM

Quote:

Originally Posted by harkapobi $View Post$

Ahh ok cool. Thank you

Is this the only way of solving this congruence? What if x was really large? this could take a long time.

And do you know what the wiggley line means at the top of the congruence sign? I didn't know how to write it in the math code. lol.

You will only have quadratic residues from 1 to 16.
They are cyclic.
Add a multiple of 16 to the x=13 above.
ALL of the residues in that quantity will be cyclic.
You then need to examine a max of 16 residues to find the result.

$7^{2199485} = 7^{13} \cdot 7^{2199472} \equiv 6 \mod 17$
.

harkapobi · #6 $Old$ November 19th, 2009, 09:14 AM

Thanks for all the help, but is there no easier way of solving this? I have another question that is similar you see,

$19^x \equiv17(mod22)$

and in the question I am told that 7 is a primitive root mod 22. So i'm assuming I need to use this somehow.

Is the only way to solve this trial and error like above?

qmech · #7 $Old$ November 19th, 2009, 10:17 AM

I'd also like to learn how to use a primitive root to help this calculation.

However, your problem is really simple. Note 19 = -3(22) and 17 = -5(22). The powers of -3 are -3, 9, -27. Note -27 = -5(22). So your x=3.