[일반] 확장 페르마소정리 이해가 잘안되는데 그냥 외워 ?

[부싼남자(112.155)]

아무리봐도 재귀적으로 되는 메커니즘이 잘이해가안돼 .. 어카지

[p플랫(urd05)]

확장 페르마 소정리?a^(오일러파이(p)=1(modp)?

[부싼남자(112.155)]

s t로 분해해서 while 돌려서 푸는건 눈으로 딸아가지고 혼자서도 식유도되고 짜지는데

[부싼남자(112.155)]

재귀적으로 들어가니간 잘이해가안됨 ㅜ

[부싼남자(112.155)]

Ax + Bx = 1 서로소라고할때 x y 정수 유도할때s[0] = 1 t[0] = 0s[1] = 0 t[1] =1 해서 s t 값 바꿔가면서 유도하는건 되는데재귀적으로 재귀(a , b){ if(a%b!=0){}

[익명(121.188)]

이건 확장 유클리드 알고리즘임

[부싼남자(112.155)]

재귀(a,b){ if(a%b!=0){ 재귀(b,a%b); tmp = y; y = x - (a/b)*y; x = tmp }else{ x=0;y=1;

[익명(121.188)]

확장 유클리드 아니냐

[익명(39.7)]

ax+by=1 근 유도하는거 확장 유클리드 맞음

[부싼남자(112.155)]

ㅇㅇ 재귀적으로 저게 이해가 안되 ㅜㅜ 몇시간찌 이해할려고 노력해도 안되는데 그냥 외우고 넘어감?

[익명(39.7)]

제일 밑에서부터 식 쓰면서 보셈