Thread: Linear congruence

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.

Since and

. . the equation becomes: .

This means: . for some integer

Solve for .[1]

Since is an integer, must be a multiple of 11.
. . The first time this happens is:

Substitute into [1]: .

Therefore: .

Thank you Soroban =)

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).