Difference between revisions of "Linear congruence"
m (→Solution 1) |
Enderramsby (talk | contribs) m |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 18: | Line 18: | ||
Multiply both sides of the congruence by <math>5</math> to get <math>25x\equiv35\pmod8</math>. Since <math>25\equiv1\pmod8</math> and <math>35\equiv3\pmod8</math>, <math>x\equiv3\pmod8</math>. | Multiply both sides of the congruence by <math>5</math> to get <math>25x\equiv35\pmod8</math>. Since <math>25\equiv1\pmod8</math> and <math>35\equiv3\pmod8</math>, <math>x\equiv3\pmod8</math>. | ||
− | [[Category: | + | [[Category:Number theory]] |
Latest revision as of 15:52, 3 August 2022
A Linear Congruence is a congruence mod p of the form
where
,
,
, and
are constants and
is the variable to be solved for.
Solving
Note that not every linear congruence has a solution. For instance, the congruence equation has no solutions. A solution is guaranteed iff
is relatively prime to
. If
and
are not relatively prime, let their greatest common divisor be
; then:
- if
divides
, there will be a solution
- if
does not divide
, there will be no solution
Example
Problem
Given , find
.
Solution 1
, so
. Thus,
. Note that we can divide by
because
and
are relatively prime.
Solution 2
Multiply both sides of the congruence by to get
. Since
and
,
.