Calculate $\phi(n)$ using Euler's totient

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
N = (p-1)*(q-1)

#882564595536224140639625987657529300394956519977044270821168

Extended Euclidean Algorithm

$$de - y(\phi(n)) \equiv 1 \pmod{\phi(n)}$$

$882564595536224140639625987657529300394956519977044270821168 = 13466661512370479891353372715527553906876367852923451955*65537 + 46333$

$65537 = 1*46333 + 19204$

$46333 = 2*19204 + 7925$

$19204 = 2*7925 + 3354$

$7925 = 2*3354 + 1217$

$3354 = 2*1217 + 920$

$1217 + 1*920 + 297$

$920 = 3*297 + 29$

$297 = 10*29 + 7$

$29 = 4*7 + 1$ (GCD: 1)

$1 = 29 - 4*7$

$= 29 - 4*(297 - 10*29) = 41*29 - 4*297$

$= 41(920-3*297) - 4*297 = 41*920 - 127*297$

$= 41*920 - 127(1217 - 1*920) = 168*920 - 127*1217$

$= 168(3354 - 2*1217) - 127*1217 = 168*3354 - 463*1217$

$= 168*3354 - 463(7925 - 2*3354) = 1094*3354 - 463*7925$

$= 1094*(19204 - 2*7925) - 463*7925 = 1094*19204 - 2651*7925$

$= 1094*19204 - 2651*(46333 - 2*19204) = 6396*19204 - 2651*46333$

$= 6396*(65537 - 1*46333) - 2651*46333 = 6396*65537 - 9047*46333$

$= 6396*65537 - 9047*(882564595536224140639625987657529300394956519977044270821168 - 121832886702415731577073962957377780195510499965398469843281*65537) = *65537 - 9047*882564595536224140639625987657529300394956519977044270821168$

$1 = 121832886702415731577073962957377780195510499965398469843281*65537 - 9047*882564595536224140639625987657529300394956519977044270821168$

$$d = 121832886702415731577073962957377780195510499965398469843281$$

Verification

1 == 121832886702415731577073962957377780195510499965398469843281*65537 - 9047*882564595536224140639625987657529300394956519977044270821168
#True