Linear Congruence

**clockingly** · September 27th 2007, 04:03 PM

The following was confusing me, so any help/explanations would be greatly appreciated!

Find all incongruent solutions to the following linear congruence:

21x ≡ 14 (mod 91)

**ThePerfectHacker** · September 29th 2007, 04:12 PM

Originally Posted by clockingly

The following was confusing me, so any help/explanations would be greatly appreciated!

Find all incongruent solutions to the following linear congruence:

21x ≡ 14 (mod 91)

$\gcd(21,91)=7$ and $7|14$ so there shall be $7$ solutions in each congruence class. By inspection we see that $x\equiv 5$ is one equivalence class which solves this. By theorem it means $5 + \frac{91}{7}t$ for $t=0,1,...,6$ shall all be solutions.

**topsquark** · September 30th 2007, 07:07 AM

Originally Posted by ThePerfectHacker

$\gcd(21,91)=7$ and $7|14$ so there shall be $7$ solutions in each congruence class. By inspection we see that $x\equiv 5$ is one equivalence class which solves this. By theorem it means $5 + \frac{91}{7}t$ for $t=0,1,...,6$ shall all be solutions.

By "incongruent" solutions the question is asking for all distinct residue classes that solve the equation?

-Dan

**ThePerfectHacker** · September 30th 2007, 08:05 AM

Originally Posted by topsquark

By "incongruent" solutions the question is asking for all distinct residue classes that solve the equation?

-Dan

Yes.

For example $x\equiv 2 (\bmod 4)$ the solutions $x=2,6$ are really the same ("congruent") solutions because they are contained in the same equivalence class (equivalence class mod $4$ *)

*)The congruence classes are $\{...,-4,0,4,...\} , \{...,-3,1,5,...\}, \{...,-2,2,6,...\}, \{...,-1,3,7,...\}$ . So $x=2,6$ are in the same equivalence class.

**duggaboy** · June 3rd 2008, 10:04 AM

so if showing the incongruences would it be x=-12=14 (mod13)??

Thread: Linear Congruence

LinkBack

Thread Tools

Display

Linear Congruence

hmm

Similar Math Help Forum Discussions

Solve linear congruence

Linear Congruence

Solving a linear congruence

non-linear congruence proof

Linear congruence

Search Tags