Posted by Jane on Friday, November 23, 2007 at 5:26pm.
I'm not sure how to start part(a). I believe part (b) is correct, but just in case I would like to make sure it's correct.
(a) Explain p^(q1) = 1 modq , If p and
q are distinct primes.
Ans: I was thinking of doing
something like part (b) but I
felt it was somehow wrong
because I wouldn't know how to
go from there.
(b) Determine 17^(98) mod 7 (give
answer in mod 7)
Ans: a=17, p=7 a^(p1)=1 mod p
==> 17^6 = 1 mod 7
[17]^6 = [1]
[17]^98= [(17)^6]^(16) * (17)^2
\__________/

[1]^16 * [17]^2 = 289
Therefore, 17^98 = 289 mod7
 ***Discrete Math ***  Count Iblis, Friday, November 23, 2007 at 5:44pm
Part a:
(all expressions are Mod q)
Consider the q1 numbers p, 2p, 3p, 4p, 5p,...,(q1)p.
All these numbers are different and nonzero. If ap = bp and p and q don't have divisors in common then a = b. So, a  b must be zero or a multiple of q, which means that all the q  1 multiples of p are different and nonzero.
Since there are only q1 nonzero numbers Mod q:
1, 2, 3, ... q1,
this means that the numbers
p, 2p, 3p, 4p, 5p,...,(q1)p
are just the numbers
1, 2, 3,... q1
but in some different order.
This means that:
1*2*3*4*...*(q1) =
p*(2p)*(3p)*(4p)*...*(q1)p.
We can write:
p*(2p)*(3p)*(4p)*...*(q1)p =
p^(q1) *1*2*3*...*(q1)
And it follows that:
p^(q1) = 1
I b)
You can simplify a but more by using that 17 = 3
So, you get 3^2 = 9 = 2 as the answer.
Answer This Question
Related Questions
 *** Discrete Math ***  I have solved parts of the question, but I want to know ...
 Geography  I just want to make sure that I have the correct answers for 2 ...
 Algebra IIPlease check fpr explanation  I have a question concerning this ...
 *** Discrete Math ***  I would like to know if my answers are correct. I also ...
 Organic chemisty(Please check)  When drawing a kekule structure for CH3CH2OH(...
 philosophy  I have to write a 1 page paper "presenting what i believe the world...
 Physics  I had a two part question in which I'm fairly sure I did the first ...
 Algebra  Consider the equation 5x + 2y = 30. Part 1: On your own paper, graph ...
 algebra  Consider the equation 7x + 3y = 42. Part 1: On your own paper, graph ...
 physics(check my answer)  A 60.0 kg person bends his knees and then jumps ...
More Related Questions