-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?

  • 0
    Thank you for edi$t$i$n$g and leave the term [2,3] and answer for the rest2011-08-21

1 Answers 1

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.