Hi, this is my first post, I'm having problems with this
Solve the linear congruence 35x ≡ 47 (mod 24)
I'm a little confused with simplification, tnks.
Hello, frankitm!
Welcome aboard!
I have a solution using "ordinary" algebra.
$\displaystyle \text{Solve the linear congruence: }\:35x \:\equiv\:47\text{ (mod 24)}$
Since $\displaystyle 35 \equiv 11\text{ (mod 24)}$ and $\displaystyle 47 \equiv 23\text{ (mod 24)}$
. . the equation becomes: .$\displaystyle 11x\,\equiv\,23\text{ (mod 24)}$
This means: .$\displaystyle 11x \:=\:24a + 23$ for some integer $\displaystyle a.$
Solve for $\displaystyle x\!:\;x \:=\:\frac{24a+23}{11} \quad\Rightarrow\quad x \:=\:2a + 2 + \frac{2a+1}{11}$ .[1]
Since $\displaystyle x$ is an integer, $\displaystyle 2a+1$ must be a multiple of 11.
. . The first time this happens is: $\displaystyle a = 5$
Substitute into [1]: .$\displaystyle x \:=\:2(5) + 2 + \frac{2(5)+1}{11}$
Therefore: .$\displaystyle x \:=\:13$
suppose we knew that there was some "magic" integer k such that:
35k = 1 (mod 24)
then from 35x = 47 (mod 24) we could deduce:
k(35x) = 47k (mod 24)
(35k)x = 47k (mod 24)
1x = 47k (mod 24)
x = 47k (mod 24).
so what could this "magic number" k be?
well, as it turns out: gcd(35,24) = 1. this means that there are INTEGERS a,b with 35a + 24b = 1 (this is called Bezout's identity).
if we take both sides mod 24, we get:
35a = 1 (mod 24), so "a" would be the "k" we were looking for!
we can, in fact, do a little better:
35 = 11 (mod 24) which means:
35 = 11 + 24n (for n = 1, in fact)
thus 35k = (11 + 24)k = 11k + 24k, so 35k = 11k (mod 24).
11 is a smaller number to work with than 35, so we're actually looking for an a and b with:
11a + 24b = 1.
here's how we find a:
24 = 2*11 + 2
11 = 5*2 + 1 <--gcd right here!
so 1 = 11 - (5*2), and 2 = 24 - (2*11), so:
1 = 11 - 5*(24 - 2*11) = 11 - 5*24 + 10*11 = 11*11 + (-5)*24. so a = 11, and b = -5 (but we don't need b now. goodbye!).
this means that 11*11 = 1 (mod 24) (and indeed, 121 is in fact congruent to 1 mod 24, since 121 = 5*24 + 1).
we can also do a little better on the right-hand side of the congruence, since 47 = 23 (mod 24).
so instead of solving 35x = 47 (mod 24), we can solve the slightly easier problem:
11x = 23 (mod 24).
and, just as above, multiplying both sides by 11 (mod 24), we get:
x = 23*11 (mod 24).
now 23*11 = 253 = 13 + 240 = 13 + 10*24, so x = 13 (mod 24).
does this work?
let x = 13 + 24n (where n might be ANY integer).
then 35x = 35(13 + 24n) = 455 + 840n = 47 + 408 + 840n = 47 + 24(17 + 35n).
since 17 + 35n is surely an integer when n is, we conclude when x = 13 + 24n,
then 35x = 47 + 24k, where k = 17 + 35n, that is:
35x = 47 (mod 24).