***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. 👍
  2. 👎
  3. 👁
  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. 👍
    2. 👎

Respond to this Question

First Name

Your Response

Similar Questions

  1. math...

    A. Solve a-9=20 I did 20+9=29 29-9=20 a=29 Part b solve b-9>20 I did b-9>20 b-9+9>20+9 b>29 Part c how is solving the equation in part a similar to solving the inequality in part b? I put They are both using the same numbers. Part

  2. 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

  3. 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)

  4. physics

    A 9.3 kg firework is launched straight up and at its maximum height 45 m it explodes into three parts. Part A (0.5 kg) moves straight down and lands 0.29 seconds after the explosion. Part B (1 kg) moves horizontally to the right

  1. CHRIST MATH

    Divide 20 into 4 parts which are in AP such that ratio between the product of the 1st part and the 4th part to the 2nd and 3rd part is 2:3 find the AP

  2. 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

  3. Calc

    Let f be the function that contains the point (-1,8) and satisfies the differential equation dy/dx=10/(x^2+1) (a) Write the equation of the tangent to f at x=-1. (b) Use your equation in part a to estimate f(0). (c) We know that

  4. 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

  1. 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

  2. lal

    present and past participle i have to write if each participle are past or present. are my answers correct 1. everyone has wondered(past participle)what the great detective was thinking(present participle) 2. carol has

  3. math

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

  4. Mathematics

    Tran has made a plan to help him study for his math exam. He has broken the material into two parts: part A and part B. He has only 2 hours over the course of the next week to study, and wants to spend twice as much time studying

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