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
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.
(a) To explain the equation p^(q-1) = 1 mod q, where p and q are distinct primes, we need to understand the concept of modular arithmetic. In modular arithmetic, we only consider remainders when dividing by a certain number, also known as the modulus.
In this case, we are considering the equation p^(q-1) = 1 mod q. This means that when we raise the number p to the power of (q-1) and take the remainder when divided by q, the result is 1.
To start proving this equation, we can use Fermat's Little Theorem, which states that if p is a prime number and a is any positive integer less than p, then a^(p-1) is congruent to 1 mod p.
Now, since p and q are distinct primes, we can apply Fermat's Little Theorem to both p and q.
Let's consider p first. According to Fermat's Little Theorem, we can write p^(p-1) = 1 mod p.
Simplifying this further, we can divide both sides by p to get p^(p-1) / p = 1 / p mod p.
Since p is prime, p does not divide p^(p-1), so we can cancel the p on the left side to get p^(p-2) = 1 / p mod p.
Now, let's move on to q. By Fermat's Little Theorem, we have q^(q-1) = 1 mod q.
Similar to what we did for p, we can divide both sides by q to get q^(q-1) / q = 1 / q mod q.
Since q is prime, q does not divide q^(q-1), so we can cancel the q on the left side to get q^(q-2) = 1 / q mod q.
Based on the above, we have p^(p-2) = 1 / p mod p and q^(q-2) = 1 / q mod q.
Now, notice that p and q are distinct primes, meaning they are not equal. Therefore, p-2 and q-2 are both positive integers.
Now, let's consider the equation p^(q-1) = 1 mod q. We can rewrite it as p^(q-1) = kq + 1 for some integer k.
We can substitute the value of q-2 from the equation q^(q-2) = 1 / q mod q into the equation p^(q-1), as follows:
p^(q-1) = p^((q-2) + 1) = p^(q-2) * p^1.
Since p^(q-2) = 1 / p mod q (from our earlier derivation), we can substitute it into our equation:
p^(q-1) = (1 / p) * p = 1 mod q.
Therefore, we have proved that p^(q-1) = 1 mod q for distinct primes p and q.
(b) Let's determine 17^(98) mod 7.
To solve this problem, we can use the properties of modular arithmetic.
Given the equation a^(p-1) = 1 mod p, we can apply it to our case where a = 17 and p = 7.
According to the equation, 17^(7-1) = 17^6 = 1 mod 7.
This means that when we raise 17 to the power of 6 and take the remainder when divided by 7, the result is 1.
Now, let's calculate 17^(98) mod 7.
We can rewrite 17^(98) as (17^6)^(16) * 17^2.
Since 17^6 = 1 mod 7, we can substitute it into our equation:
17^(98) mod 7 = (17^6)^(16) * 17^2 mod 7.
Simplifying further, we have:
17^(98) mod 7 = (1)^(16) * 17^2 mod 7.
Since any number raised to the power of 0 is equal to 1, we can simplify our equation as:
17^(98) mod 7 = 1 * 17^2 mod 7.
Calculating 17^2, we get:
17^(98) mod 7 = 1 * 289 mod 7.
Finally, we can divide 289 by 7 to get the remainder:
17^(98) mod 7 = 289 mod 7 = 4.
Therefore, 17^(98) mod 7 is equal to 4.