6
$\begingroup$

I have been trying very hard to solve this type of congruence equation: $ax = b \pmod n$ and finally managed to actually solve a few by using properties like $\text{if}\quad \begin{cases} ax=b \pmod n \\ cx=d \pmod n \end{cases} \quad\text{then}\quad acx = bd \pmod n$ but still there are some simple congruences which I am not able to solve like $25x=15\pmod{29}.$

I tried to make use of both above and transitive property of congruences but that is not working here.

Now, I wanted to ask if is there any other method to solve congruences. I am asking this because I have very little knowledge of congruences. I have Burton's book of number theory and that helped me much better than Zuckerman's text did. But, still there are some topics that I am not able to do yet.

  • 0
    I answered$a$closely related question just yesterday, and linked to yet another closely related question that I had answered some time ago. See my answer below. I linked to that much earlier answer. It pretty much covers the situation when you're working modulo a prime number.2012-08-18

6 Answers 6

-1

Solution using Euler's function: enter image description here

  • 0
    Please use LaTeX syntax when posting answers! Also, usually it is better to not post answers when many answers already exist!2016-06-01
3

$25x\equiv 15\pmod{29}\tag{1}$

$29$ is a prime number, an one can show (I think Gauss showed) that that implies every number in $\{1,2,3,\ldots,28\}$ must have a mod-$29$ multiplicative inverse within that set. So let's find the inverse $y$ of $25$, so that $25y\equiv1\pmod{29}$, and then multiply both sides of $(1)$ by $y$, getting $ x\equiv15y\pmod{29}. $ We want: $ \begin{align} 25y & \equiv 1 \pmod {29} \\ 25y & = 1 - 29z \\ 25y+29z & = 1. \end{align} $

If we divide $29$ by $25$, we get $1$, with remainder $4$: $ 29-\{1\}25 = 4\tag{2} $ Now divide $25$ by $4$, getting $6$, with remainder $1$: $ 25-\{6\}4 = 1\tag{3} $ Because $(2)$ is true, we can put $29-\{1\}25$ in place of $4$ in $(2)$: $ 25-\{6\}(29-\{1\}25). $ Now collect the $29$s and $25$s: $ -\{6\}29 + \{7\}25 = 1.\tag{4} $ So we have $y=7$ and $z=-6$.

Thus $(4)$ tells us that $ 7\cdot25\equiv 1\pmod{29} $

Thus multiply both sides of $(1)$ by $7$: $ x\equiv7\cdot15\equiv 18 \pmod{29}. $ See Calculating the Modular Multiplicative Inverse without all those strange looking symbols for the way to find the inverse of $322$ mod $701$. It turns out to be $455$.

  • 0
    Hi, can you explain why to multiply by 7 in both sides does "kill" the 25? As far as I see we get $7 \cdot 25 x \equiv 15 \cdot 7 \equiv 18 (mod 29)$2016-11-17
2

A related problem. First step we simplify the congruence as $ 25 x \equiv 15\bmod{29} \Rightarrow 5 x \equiv 3 \bmod 29\,, $ since $\gcd(5,29)=1\,.$

You can use the following algorithm,

if $ a x \equiv b \bmod m$, then you can reduce it to $ m y \equiv -b \bmod a)\,.$ If $y_0$ is a solution for of the reduced congruence, then $x_0$ defined by $ x_0 = \frac{my_0+b}{a} \,.$ is a solution of the original congruence.

Applying this algorithm to your problem, we can reduce our congruence to

$ 29 y \equiv -3 \bmod 5 \Rightarrow 4 y \equiv -3 \bmod 5\,. $ You can see now by inspection that $y_0 = 3 $ is a solution of the last congruence. Substituting in $ x_0 = \frac{my_0+b} a =\frac{29.3+3}{5}=18\,. $

1

Hint $\ $ Since $\rm\,gcd(25,29) = 1,\:$ Bezout $\rm\:\Rightarrow\:1/25\:$ exists mod $\,29.\:$ Therefore

$\rm mod\ 29\!:\,\ 25\,x\equiv 15\:\Rightarrow\:x\equiv \frac{15}{25}\equiv\frac{3}{5}\equiv\frac{3\cdot 6}{5\cdot 6}\equiv\frac{18}1$

  • 0
    Bill, could I ask you a little thing in the chat?2012-08-18
0

A linear congruence equation is equivalent to a linear equation where all coefficients and all variables are from the Set of Integers (Z). The linear congruence equation ax = b (mod n) may be rewritten as ax1 = b - nx2 where x1, x2 -E- Z. For example 25x = 15 (mod 29) may be rewritten as 25x1 = 15 - 29x2.

It is possible to solve the equation by judiciously adding variables and equations, considering the original equation plus the new equations as a system of linear equations, and solving the linear system of equations using back substitution. In every step if there is a GCF, greatest common factor, greater than 1 for all coefficients and the right-hand constant in the current equation, then the GCF must be removed before continuing.

A solution to the example 25x = 15 (mod 29) may be found here: How I Solved the Linear Congruence 25x = 15 (mod 29). The following is an image of the page.

enter image description here