Question

Please solve all parts of the question

6. (10 points 5+5) We want to prove by contradiction that, for all integers k not divisible by p, if p is prime then no two different numbers in the set Ak(k,2k, 3k.. 1)k) are congruent mod p. (a) Clearly state the assumption to begin the proof by contradiction. (b) Complete the proof by making two observations regarding this assumption that immediately lead to a contradiction

Answer 1

Please upvote if you like the answer, as it helps the community a lot.

Also if you have any doubts, feel free to ask in comments, we will reach you ASAP.

SOLUTION:

Given,

P : a prime number

k: a number not divisible by P

We are also given a set of numbers A_k: {k, 2k, 3k, .... , (P-1)k}.

Very Important:

Note that NONE of the numbers in the set A_k can be divisible by P, because

• k is not divisible by P and

• P is a prime number

i.e. (m*k) mod P not equals 0 for any value of m between 1 to P-1.

To prove:

No two numbers in the given set A_k are congruent mod P

In other words,

There exists NO i,j between [1,P-1] (i not equals j), such that

(i*k) mod P = (j*k) mod P

Assumption:

Since i and j are not equal, it is safe to assume one of them to be less than the other.

Here, we assume, j<i.

Now, let us say for some time that, the statement below was possible

(i*k) mod P = (j*k) mod P

= some constant (say X)

So we can write

(i*k) mod P - (j*k) mod P = (X-X) mod P = 0 mod P

((i-j)*k) mod P = 0 mod P

(since i>j and i,j is between [1,P-1])

(m*k) mod P = 0

Which is not possible at all, as written in Given section.

Hence,

Proved

No two numbers in the given set A_k can be congruent mod P