A P_r megoldáshalmaz minden eleme kielégíti az első kongruenciát, azaz r-rel azonos modulo p^c maradékosztályban van. Következésképp a 20.4. Tétel alapján minden x\in P_r esetén létezik olyan y egész szám, hogy teljesül az alábbi egyenlet:

x=r+p^cy

Tehát tulajdonképpen azokat az y egész számokat keressük, amelyekre fennáll a második kongruencia is, azaz:

(\underbrace{r+p^cy}_{=x})^{p-1}\equiv 1\pmod{p^{c+1}}

A baloldalon szereplő zárójeles kifejezést felbontva a Korselt-kritérium (26.17. Tétel) bizonyításánál látott gondolatmenet alapján az alábbi összeget kapjuk valamilyen A_2, A_3, …, A_{p-1} együtthatókkal:

\begin{aligned}(r+p^cy)^{p-1}&=r^{p-1}+(p-1)r^{p-2}p^cy+\\&+A_2r^{p-3}p^{2c}y^2 + A_3r^{p-4}p^{3c}y^3+\ldots +A_{p-1}p^{(p-1)c}y^{p-1}\end{aligned}

Ennek a kifejezésnek az értéke modulo p^{c+1} érdekel minket, emiatt nincs szükségünk az A_2, A_3, …, A_{p-1} együtthatók pontos értékére – amelyeket egyébként a binomiális tétel alapján lehetne kiszámítani. A 3. tagtól kezdve ugyanis minden tag osztható p^{c+1}-gyel, vagy másként fogalmazva 0-val kongruens modulo p^{c+1}. Azaz tulajdonképpen az alábbi kongruencia megoldásait keressük:

\underbrace{r^{p-1}+(p-1)r^{p-2}p^cy}_{\equiv (r+p^cy)^{p-1}}\equiv 1\pmod{p^{c+1}}

A tétel szövegéből tudjuk, hogy r-re teljesül az alábbi kongruencia is:

r^{p-1}\equiv 1\pmod{p^c}

Azaz az r^{p-1} hatvány ugyanabban a modulo p^c maradékosztályban van, mint az 1 egész szám. Ám ekkor ugyancsak a 20.4. Tétel értelmében létezik olyan k_r egész szám, amelynek a segítségével az r^{p-1} hatvány felírható az alábbi alakban:

r^{p-1}=p^ck_r+1

Ezt behelyettesíthetjük a kongruenciánkba, amelynek tehát a megoldásait keressük:

\underbrace{p^ck_r+1}_{=r^{p-1}}+(p-1)r^{p-2}p^cy\equiv 1\pmod{p^{c+1}}

A 20.2. Tétel 6. pontja értelmében mindkét oldalból levonhatunk 1-et:

p^ck_r+(p-1)r^{p-2}p^cy\equiv 0\pmod{p^{c+1}}

A zárójelet felbontva az alábbit kapjuk, ahol a második tag 0-val lesz kongruens modulo p^{c+1}, így az elhagyható:

p^ck_r+\underbrace{\cancel{r^{p-2}p^{c+1}y}}_{\equiv 0}-r^{p-2}p^cy\equiv 0\pmod{p^{c+1}}

A maradék két tagból a p^c szorzótényezőt kiemelhetjük:

p^c\cdot (k_r-r^{p-2}y)\equiv 0\pmod{p^{c+1}}

Ez a kongruencia viszont a kongruenciák egyszerűsítéséről szóló 20.3. Tétel alapján akkor és csak akkor teljesül, amikor az alábbi kongruencia is:

k_r-r^{p-2}y\equiv 0\pmod p

Mindkét oldalhoz r^{p-2}y-t adva tehát tulajdonképpen az alábbi lineáris kongruencia megoldásait keressük:

r^{p-2}y\equiv k_r\pmod p

Mivel a tétel szövegéből tudjuk, hogy teljesül az r^{p-1}\equiv 1\pmod{p^c} kongruencia, ezért a 24.18. Tétel 1. pontjának értelmében az [r]_{p^c} maradékosztály nem lehet Miller-Rabin-tanúja p^c-nek. Így viszont a 23.9. Definíció utáni megjegyzés értelmében [r]_{p^c} egy redukált maradékosztály, azaz r relatív prím p^c-hez. Ez egyben azt is jelenti, hogy r prímtényezős felbontásában biztosan nem szerepel a p prímszám, amely nyilván igaz lesz r bármely hatványára is. Így például az r^{p-2} hatványra – mint a fenti lineáris kongruencia együtthatójára – is, amely tehát relatív prím a p modulushoz, azaz (r^{p-2},p)=1.

Ez biztosan osztója a lineáris kongruencia jobboldalán lévő k_r-nek, így tehát a 20.12. Tétel értelmében szükségképpen létezik megoldás. Továbbá a megoldások száma a 20.13. Tétel alapján pontosan (r^{p-2},p)=1 darab modulo p maradékosztály.

Válasszuk ki ennek az eszerint egyetlen modulo p maradékosztálynak egy tetszőleges elemét, amelyet jelöljünk y_0-val. Ekkor tehát az y=y_0+pm képlet segítségével megkapjuk az (r+p^cy)^{p-1}\equiv 1\pmod{p^{c+1}} kongruenciát kielégítő összes egész számot (és csak azokat), amennyiben m-mel befutjuk a teljes \Z halmazt. Most alkalmazzuk visszafelé az x-re bevezetett jelölésünket:

x=r+p^c\cdot (\underbrace{y_0+pm}_{=y})=r+p^cy_0+p^{c+1}m

Ez tehát azt jelenti, hogy a tételben szereplő kongruenciarendszert kielégítő P_r megoldáshalmaz összes elemét (és csak azokat) megkapjuk, amennyiben a fenti képletben szereplő m-mel befutjuk a teljes \Z halmazt. Vagyis a 20.4. Tétel értelmében P_r valóban épp egy modulo p^{c+1} maradékosztály, melynek egyik reprezentánseleme r+p^cy_0.