-2
$\begingroup$

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?

  • 5
    See [this answer](http://math.stackexchange.com/questions/44822/efficient-way-to-find-a-in-c-6a-mod-n/44826#44826).2011-08-18
  • 2
    @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.2011-08-19
  • 0
    Thank you for all posts of comments. I am giving little more explanation for third question of my post. Please see my edited one.2011-08-20
  • 0
    @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.2011-08-20
  • 1
    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?2011-08-20
  • 0
    Thank you for editing and leave the term [2,3] and answer for the rest2011-08-21

1 Answers 1