36까지의 정수 중 그와 공약수를 갖지 않는 수의 개수는 12입니다. 곱 조리법은 36을 잡아 각 소인수로 나누어떨어지는 몫을 버립니다. (1 − 1/2)를 곱해 짝수를 없애고 (1 − 1/3)을 곱해 3의 배수를 없애면 작업대는 12를 보여 줍니다. 36 = 2²·3²이므로 나눌 수 있는 소수는 이 둘뿐입니다.
두 번째 링크는 포함배제로 같은 것을 다르게 셉니다. 2의 배수 열여덟, 3의 배수 열둘, 두 번 빼졌으므로 한 번 더해지는 6의 배수 여섯입니다. 36 − 18 − 12 + 6 = 12입니다. 두 조리법은 반드시 일치해야 하며, 일치하는 이유는 2 또는 3으로 나누어떨어진다는 것이 정확히 36과 서로소가 아니라는 것이기 때문입니다. φ는 RSA의 산술이 작동하는 수입니다. 오일러 정리는 n과 서로소인 모든 a에 대해 a^φ(n) ≡ 1 (mod n)이라고 말하므로, 이 세기의 크기가 주기의 크기입니다.
답
12
읽는 방법
작업대의 36·(1 − 1/2)(1 − 1/3)입니다. 두 번째 링크는 포함배제로 센 값이고, 세 번째는 어떤 소수를 세는지 말해 주는 분해 2²·3²입니다.
출처
Euler's totient φ(36) = 36(1 − 1/2)(1 − 1/3) = 12, from his 1763 memoir on the function; the product form φ(n) = n·∏(1 − 1/p) over the primes dividing n is the standard result behind RSA key arithmetic
계산기에서 풀어 보기
이 링크는 이 문제의 숫자가 이미 입력된 알맞은 계산기를 엽니다. 위 줄은 화면에 표시되어야 하는 내용입니다. 직접 확인하세요.