• Post a New Question
• Current Questions
• Chat With Live Tutors

Homework Help: ***Discrete Math ***

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^(q-1) = 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^(p-1)=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 q-1 numbers p, 2p, 3p, 4p, 5p,...,(q-1)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 q-1 nonzero numbers Mod q:
  1, 2, 3, ... q-1,
  
  this means that the numbers
  
  p, 2p, 3p, 4p, 5p,...,(q-1)p
  
  are just the numbers
  
  1, 2, 3,... q-1
  
  but in some different order.
  
  This means that:
  
  1*2*3*4*...*(q-1) =
  
  p*(2p)*(3p)*(4p)*...*(q-1)p.
  
  We can write:
  
  p*(2p)*(3p)*(4p)*...*(q-1)p =
  
  p^(q-1) *1*2*3*...*(q-1)
  
  And it follows that:
  
  p^(q-1) = 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

First Name:
School Subject:
Answer:

Related Questions

Organic chemisty(Please check) - When drawing a kekule structure for CH3CH2OH(...
*** 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 ...
math,help - can someone show me these steps with the division like 2 --- 1 which...
English - 1. Let's do some role play. You take the part of A, and you take ...
movies - I can't believe that the final Harry Potter movie is coming out in ...
math - Consider the following binomials. A=(x^2+5x) B=(6x+30) Part 1: Factor ...
math - Consider the following binomials. A=(x^2+5x) B=(6x+30) Part 1: Factor ...
math - Consider the following binomials. A=(x^2+5x) B=(6x+30) Part 1: Factor ...
philosophy - I have to write a 1 page paper "presenting what i believe the ...

For Further Reading