***Discrete Math ***

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

  1. 👍 0
  2. 👎 0
  3. 👁 205
  1. 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.

    1. 👍 0
    2. 👎 0

Respond to this Question

First Name

Your Response

Similar Questions

  1. physics

    You shoot an arrow into the air. Two seconds later (2.00 s) the arrow has gone straight upward to a height of 30.0 m above its launch point part A:What was the arrow's initial speed?part B:How long did it take for the arrow to

  2. intro to physics

    an athlete executing a long jump leaves the ground at a 28 degree angle and lands 7.6 m away. part a )what was the takeoff speed ? part b) if this speed were increased by just 8.0% , how much longer would the jump be ? for part a)

  3. chemistry

    In part B of my question, I was asked calculate the number of atoms in 0.615 mol of 13C (mass number of this Carbon is 13). I received the correct answer of 3.70E23 atoms. However, I do not know how to do Part C of my question,

  4. Algebra

    On the first part of a trip to Carmel traveling on the​ freeway, Marge averaged 70 mph. On the rest of the​ trip, which was 25 mi longer than the first​ part, she averaged 60mph. Find the total distance to Carmel if the

  1. Science

    Maria and Sam are studying about cells, tissues, organs, and organ systems in the human body. This is a picture of the human digestive system. Each part is a different color. Each part does something different during the process

  2. physics

    I really need help on D part of the following problem: A clever engineer designs a "sprong" that obeys the force law F subscript e = -q(x - x subscript e)^3, where x subscript e is the equilibrium position of the end of the sprong

  3. algebra

    Part A: Graph the system of linear equations. Part B: Use the graph created in Part A to determine the solution to the system. Part C: Algebraically verify the solution from a Part B x + 6y = 6 y = 1/3x - 2

  4. chemistry

    In part B of my question, I was asked calculate the number of atoms in 0.462 mol of 13C (mass number of this Carbon is 13). I received the correct answer of 2.78E23 atoms. However, I do not know how to do Part C of my question,

  1. physics

    You are driving through town at 12.0 m/s when suddenly a ball rolls out in front of you. You apply the brakes and begin decelerating at 3.7 m/s2 . part A=How far do you travel before stopping? part B= When you have traveled only

  2. math

    Tran has made a plan to help him study for his math exam. He has broken down the material that he has to study into two parts: part A and part B and has, at most, 2 hours every evening over the next week to study. He wants to

  3. mathematics

    Priscilla grandmother"s fruit salad call for one part apple,one part orange,three part grapes, two parts cherry,four part strawberry . Priscilla uses the same measuring cup to measure all the fruit, so one part is equal to one cup

  4. @damon

    I am still getting the wrong answrs, can you please do me a favor and for each part list the formulas and steps i need to do in order to get the answer. thank you At serve, a tennis player aims to hit the ball horizontally. part

You can view more similar questions or ask a new question.