Випадок 2. Нехай (a,m)=d. У цьому випадку, для можливості розв'язку порівняння axº b(mod m) необхідно, щоб d ділило b, інакше порівняння узагалі виконуватися не може. Дійсно, axº b(mod m)   буває тоді, і тільки тоді, коли ax-b ділиться на m без остачі, тобто ax-b=t · m,

t Î Z, звідки b=ax-t × m , а права частина останньої рівності кратна d.

Нехай b=db₁, a=da₁, m=dm₁. Тоді обидві частини порівняння xa₁ dº b₁ d(mod m₁ d) і його модуль поділимо на d :

xa₁ º b₁ (mod m₁),

де вже а₁ і m₁ взаємно прості. Згідно випадку 1 цього пункту, таке порівняння має єдиний розв’язок x₀ :

x º x₀ (mod m₁ ) (*)

За вихідним модулем m, числа (*) утворять стільки розв’язків вихідного порівняння, скільки чисел виду (*) міститься в повній системі лишків: 0,1,2,..., m-2, m-1. Очевидно, що з чисел x=x₀+t× m в повну систему найменших невід’ємних лишків попадають лише x₀, x₀+m₁, x₀+2m₁, ..., x₀+(d-1)m₁, тобто усього d чисел. Значить у вихідного порівняння є d розв’язків.

Теорема 1. Нехай (a,m)=d . Якщо b не ділиться на d, то порівняння axº b(mod m) немає розв’язків. Якщо b кратне d, то порівняння axº b(mod m) має d розв’язків.

Приклад. Розв’язати порівняння 111x º 75(mod 321) .

Розв’язування. (111,321)=3, тому поділимо порівняння і його модуль на 3:

37x º 25(mod 107) і (37,107)=1.

Включаємо алгоритм Евкліда (підкреслені неповні частки):

107=37 × 2+33

37=33 × 1+4

33=4 × 8+1

4=1 × 4

Маємо n=4 і ланцюговий дріб такий:

Таблиця для знаходження чисельників прямуючих дробів:

qn	0	2	1	8	4
Pn	1	2	3	26	107

Одержуємо, x º (-1)³ × 26 × 25 º -650(mod 107) º -8(mod 107) º 99(mod 107).

Три розв’язки вихідного порівняння:

xº 99(mod 321), xº 206(mod 321), xº 313(mod 321),

і інших розв’язків немає.

Розглянемо інші способи розв’язування порівнянь першого ступеня. Ці способи викладаються далі у виді теорем.