Difference between revisions of "Linear congruence"
(→Solution) |
Enderramsby (talk | contribs) m |
||
(5 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | A '''Linear Congruence''' is a [[congruence]] mod p of the form | + | A '''Linear Congruence''' is a [[congruence]] [[modular arithmetic|mod]] p of the form |
+ | <cmath>ax+b\equiv c\pmod{p}</cmath> | ||
+ | where <math>a</math>, <math>b</math>, <math>c</math>, and <math>p</math> are [[constant]]s and <math>x</math> is the [[variable]] to be solved for. | ||
− | <math> | + | ==Solving== |
+ | Note that not every linear congruence has a solution. For instance, the congruence equation <math>2x\equiv3\pmod8</math> has no solutions. A solution is guaranteed [[iff]] <math>a</math> is [[relatively prime]] to <math>p</math>. If <math>a</math> and <math>p</math> are not relatively prime, let their [[greatest common divisor]] be <math>d</math>; then: | ||
+ | * if <math>d</math> [[divide]]s <math>b</math>, there will be a solution <math>\pmod{\frac{p}{d}}</math> | ||
+ | * if <math>d</math> does not divide <math>b</math>, there will be no solution | ||
− | + | ==Example== | |
+ | ===Problem=== | ||
+ | Given <math>5x\equiv7\pmod8</math>, find <math>x</math>. | ||
+ | ===Solution 1=== | ||
+ | <math>7\equiv15\pmod8</math>, so <math>5x\equiv15\pmod8</math>. Thus, <math>x\equiv3\pmod 8</math>. Note that we can divide by <math>5</math> because <math>5</math> and <math>8</math> are relatively prime. | ||
− | == | + | ===Solution 2=== |
+ | 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:Number theory]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Latest revision as of 14: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 , .