울프람알파도 못 푼 방정식을 풀었다. 으하하하ㅎ





확장된 유클리드 호제법
ex) 22x + 60y = gcd(22,60)
1단계 : gcd(5454888,55555) 최대공약수 구하기 1

2단계 : 방정식 만들기
5454888 x + 55555 y = 1

3. 계산하기

5454888 = 98 * 55555 + 10498 -> 10498 = 5454888 - 98*55555 -> 10498=a-98*b
계수a0 = 1, 계수b0 = -98
55555 = 5 * 10498 + 3065 -> 3065 = 55555 - 5*10498 -> 3065=b-5*(a-98*b) -> -5a+491b
계수a1 = -5, 계수b1 = 491
10498 = 3 * 3065 + 1303 -> 1303 = 10498 - 3*3065 -> 1303=a-98*b-3*(-5a+491b) -> 16a-1571b
계수a2 = 16, 계수b2 = -1571
3065 = 2 * 1303 + 459 -> 459 = 3065 - 2*1303 -> 459=-5a+491b-2*(16a-1571b) -> -37a+3633b
계수a3 = -37, 계수b3 = 3633
1303 = 2 * 459 + 385 -> 385 = 1303 - 2*459 -> 385=16a-1571b-2*(-37a+3633b) -> 90a-8837b
계수a4 = 90, 계수b4 = -8837
459 = 1 * 385 + 74 -> 74 = 459 - 1*385 -> 74=-37a+3633b-1*(90a-8837b) -> -127a+12470b
계수a5 = -127, 계수b5 = 12470
385 = 5 * 74 + 15 -> 15 = 385 - 5*74 -> 15=90a-8837b-5*(-127a+12470b) -> 725a-71187b
계수a6 = 725, 계수b6 = -71187
74 = 4 * 15 + 14 -> 14 = 74 - 4*15 -> 14=-127a+12470b-4*(725a-71187b) -> -3027a+297218b
계수a7 = -3027, 계수b7 = 297218
15 = 1 * 14 + 1 -> 1 = 15 - 1*14 -> 1=725a-71187b-1*(-3027a+297218b) -> 3752a-368405b
계수a8 = 3752, 계수b8 = -368405

3752a-368405b


(3752) * 5454888 + (-368405) * 55555 = 1