Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
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
Thank you for all posts of comments. I am giving little more explanation for third question of my post. Please see my edited one. – Gandhi Aug 20 '11 at 15:06
@Arturo and others involved in the previous discussion: In view of Gandhi's most recent edit, I am removing the long (off-topic) discussion on etiquette. @ Gandhi: still, it would be better if you would edit the original post to read "How can I prove such and such fact?" instead of "Prove such and such fact." On a Question and Answer site, we prefer it if you ask questions, and not issue demands. – Willie Wong Aug 20 '11 at 16:02
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

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.