[Verse 1]
When you see a times x congruent b mod n
There's a question that you need to ask right then
Does the gcd of a and n divide into b?
If it doesn't then there's no solution, you see
[Chorus]
GCD divides b, solutions exist
Count them up, they're on the list
D solutions mod n you'll find
Where d is gcd, keep this in mind
Linear congruences follow the rule
GCD divides b is your main tool
[Verse 2]
Calculate gcd of a and n with care
If it goes into b evenly, solutions are there
The number of answers equals d exactly
Modulo n they spread out so perfectly
[Chorus]
GCD divides b, solutions exist
Count them up, they're on the list
D solutions mod n you'll find
Where d is gcd, keep this in mind
Linear congruences follow the rule
GCD divides b is your main tool
[Bridge]
Special case when gcd equals one
Then a and n share no common fun
Coprime they are, unique solution's here
Extended Euclidean makes the path clear
Find a inverse modulo n
Multiply by b and you'll win
X congruent a inverse times b mod n
[Verse 3]
Use Extended Euclidean Algorithm's might
To find the inverse when gcd is one right
Back substitution shows the way
To solve your congruence equation today
[Chorus]
GCD divides b, solutions exist
Count them up, they're on the list
D solutions mod n you'll find
Where d is gcd, keep this in mind
Linear congruences follow the rule
GCD divides b is your main tool
[Outro]
When d divides b the equation's solved
Count d solutions, mystery resolved