연속제곱법: a^k (mod m) 빨리 계산하기k를 2의 거듭제곱의 합으로 표현k = u0*A0 + u1*A1 +...+ ur*Ar각각의 제곱들을 mod 연산하기a ≡ A0 (mod m)a^2 ≡ A1 (mod m)a^4 ≡ A2 (mod m)a^8 ≡ A3 (mod m)...a^r ≡ Ar (mod m)구한 A들을 가지고 연산하기A0^u0*A1^u1*...*Ar^ur ≡ a^(u02^0 + u12^1 + ... ur2^r) ≡ a^k (mod m) 법 m에 대한 k제곱근 구하기x^k ≡ b (mod m)에서gcd(b, m)=1, gcd(k, ϕ(m)) = 1이라면ϕ(m) 계산하기ku-ϕ(m)v = 1인 양의 정수 u, v를 구함b^u를 연속제곱법으로 계산x ≡ b^u (mod m)증명x^(ku) ≡ x..

임의의 원시 피타고라스 세 수 (a, b, c)가 있다. 이때 다음을 보여라a or b가 3의 배수인가?언제 a, b, c가 5의 배수인가?a or b가 3의 배수인가?정수 집합을 mod 3의 동치관계로 분할해보자.즉, a, b, c = 3k, 3k+1, 3k+2 꼴이다. (k=정수)만약 a, b 모두 3의 배수가 아니라면?a, b = 3k+1 or 3k+2 꼴이다.a^2 + b^2 = c^2에서 mod 3을 보기 위해 (3k+1)^2, (3k+2)^2에 대한 mod 3을 봐보자.(3k+1)^2 ≡ 3(3k^2+2k)+1 ≡ 1 (mod 3)(3k+2)^2 ≡ 3(3k^2+4k+1)+1 ≡ 1 (mod 3)따라서 a^2+b^2 ≡ 2 (mod 3)일 수밖에 없다.그러나, c가 될 수 있는 3k, 3k+1..