***Discrete Math ***

posted by .

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 *** -

    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.

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. *** Discrete Math ***

    I have solved parts of the question, but I want to know if they are correct. Other parts I'm not sure how to do, like part b and c. g(x)=2x+1 Define g^3= g^2 o g,...,g^n =g^(n-1) o g (where "o" means composition) a) Give rules for …
  2. *** Discrete Math ***

    I would like to know if my answers are correct. I also need help solving some exercises the right way. (a) Explain why [13] is invertible in Z50. Ans: it's invertible because there's some [t]E Z50 such that [13][t]=1 (b) Use the usual …
  3. philosophy

    I have to write a 1 page paper "presenting what i believe the world is made of and explain why i believe that to be the case" and he said it doesn't deal with like water and land, so im not sure what he means, any help would be great.
  4. physics(check my answer)

    A 60.0 kg person bends his knees and then jumps straight up. After his feet leave the floor, his motion is unaffected by air resistance and his center of mass rises by a maximum of 14.9 cm. Model the floor as completely solid and motionless. …
  5. algebra

    Consider the equation 7x + 3y = 42. Part 1: On your own paper, graph this equation using the slope-intercept method. In the space provided, explain, in words, each step of the procedure you used. Make sure to use complete sentences …
  6. Algebra

    Consider the equation 5x + 2y = 30. Part 1: On your own paper, graph this equation using the slope-intercept method. In the space provided, explain, in words, each step of the procedure you used. Make sure to use complete sentences …
  7. Geography

    I just want to make sure that I have the correct answers for 2 questions: 1. The western part of North America is more mountainous than the eastern part. 2. Chile is the longest country in South America.
  8. Algebra II-Please check fpr explanation

    I have a question concerning this problem:I just want to make sure my formulas are correct before I do problem It is a hyperbola equation (y-4)^2/49 - (x-6)^2/72 = 1 1.It is a vertical hyperbola, correct?
  9. Physics

    I had a two part question in which I'm fairly sure I did the first part correct, but part b I am unsure about. For part a, I had to determine the magnitude of the net electric field at the origin, which I got E= 1.7 X 10^7 N/C. Part …
  10. Organic chemisty(Please check)

    When drawing a kekule structure for CH3CH2OH(alcohol) do I leave the OH at the end just like it is (OH) or would it be shown as O-H?

More Similar Questions