Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that the linear congruence mx = p mod q, where gcd of (m,q) = 1, has a unique solution x = $p_0$ mod q, where $p_0$ belongs to {(p + qk)/m} where k = 0 to m-1.

Also, prove that, If gcd of (m, q) = d and d|p, then the linear congruence mx = p mod q, has d distinct (in-congruent) solutions modulo q.

EDIT also Prove that, the linear congruence cx = a mod b, where gcd(c, b) = 1 has solution $x = a(1-b^{\phi(c)})/c \mod b$.

EDIT The third question of my previous post can be read as follows. The linear congruence $cx \equiv a \pmod b$ and $\gcd (c, b) = 1$ has solution in the form of $x \equiv a(1-b^{\phi(c)})/c \pmod b$.

A standard method of solving linear congruences involves Euler's phi function [2,3], or totient, denoted by $\phi$. The totient $\phi(b)$ enumerates the positive integers less than $b$ which are relatively prime to $b$. Euler's extension of Fermat's theorem states that $c^{\phi(b)} \equiv 1 \pmod b$, if $\gcd(c, b) = 1$ and multiplying the linear congruence $cx \equiv a \pmod b$ through by the factor $c^{\phi(b)-1}$ gives $x \equiv ac^{\phi(b)-1} \pmod b$.

Edited If gcd(c, b) = d and d|a, then the linear congruence cx = a mod b has d distinct solutions x = [$x_0$, $x_0$ + $b_0$, ... , $x_0$ + $b_0$(d - 1)] mod b, where a = $a_0$ d, b = $b_0$ d, c = $c_0$ d, and $x_0$$ \equiv $$a_0$$(1-$$b_0$$^{\phi(c_0)})/$$c_0$$ \pmod b$. Can you generalize?

share|cite|improve this question
What have you attempted so far? This looks like homework, if so just add the homework tag. Lastly, try not to use the imperative form when asking questions, some people interpret it as rude. – Eric Naslund Aug 18 '11 at 17:39
Do you think it as home work problem??? Great! the last question demands the originality of the mathematician. I think, no mathematician will say like you, if he/she understand the third part of my post. – Gandhi Aug 18 '11 at 18:03
See this answer. – Arturo Magidin Aug 18 '11 at 20:37
@Gandhi, the first two parts are standard results about linear congruences, discussed in many intro Number Theory textbooks. The proofs are a bit long to write out, if one starts by not assuming any previous knowledge, so it's probably best if you seek out a textbook, or possibly search the web for "linear congruence" or some such keyphrase. The third question, all these symbols $a$, $b$, $c$, and $k$ seem to come from nowhere, with no explanation. Maybe if you gave an example it would be clearer just what you are talking about. – Gerry Myerson Aug 19 '11 at 13:48
I have edited some TeX into part of the question to improve readability. There is something very strange in the third sentence, which begins with $m,p,q$ but ends with $a,b,c$. I hope OP will edit to clarify. I also left in the [2,3] in the last part though I don't know what it means. The "third question" doesn't seem to be a question, as the last paragraph seems to answer it. Gandhi, is there still something you want to know? – Gerry Myerson Aug 20 '11 at 23:46

1 Answer 1

We're asked to prove that if $\gcd(b,c)=1$ then the congruence $cx\equiv a\pmod b$ has the solution $x\equiv a(1-b^{\phi(c)})/c\pmod b$, where $\phi$ is the euler phi-function.

Note that by Euler's Theorem $b^{\phi(c)}\equiv1\pmod c$ so $(1-b^{\phi(c)})/c$ is an integer. If $x\equiv a(1-b^{\phi(c)})/c\pmod b$ then $cx\equiv a(1-b^{\phi(c)})\equiv a\pmod b$ since obviously $b^{\phi(c)}\equiv0\pmod b$. So we have proved that the formula for $x$ gives a solution to the congruence.

share|cite|improve this answer
Thank you so much for your solution. really very good but I need little more. see new edited one. – Gandhi Aug 21 '11 at 15:38
@Gandhi, you know what I think about editing a question to ask for more after the question has already been answered. – Gerry Myerson Aug 22 '11 at 13:44
ok, Thank you sir. – Gandhi Aug 22 '11 at 16:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.