Congruency

Prove::::::::

If gcd(a,n)=1,then the integers c,c+a,c+2a,c+3a,...........................,c+(n-1)a form a complete set of reidues modulo n, for any c.

6 Answers

39
Dr.House ·

please explain your question in a detailed way

1
Anirban ·

what more clarification do u need

341
Hari Shankar ·

c≡0 is obvious. Now look at the (n-1) numbers c+a, c+2a,...,c+(n-1)a. Suppose any two have the same residue then their difference should be divisible by n. Prove this cannot happen.

39
Dr.House ·

anirban, just state what u mean by the question in a simpler way

i am not a dumb guy tto ask u to explain your question

put your question in mathematical terms

i would be even greatful if u tell me whats your approach

1
Anirban ·

@prophet sir

Perhaps this will seem to u a dumb q but I cannot understand why c≡0 is obvious.It is not mentioned that c is divisible by n

1
Ricky ·

Let S = { c , c + a , c + 2 a . . . . . . }

Let us assume , contrary to the the hypothesis , that S does not form a complete set of residues

modulo n . Then there exist 2 distinct positive integers " d " and " c " with b < d < n ( without loss

of generality ) such that ,

c + a + d ≡ c + a + b ( mod n )

It follows that , d ≡ b ( mod n )

Which obviously is a contradiction since , b < d < n implies that ------ d - b < n .

QED .

Your Answer

Close [X]