 nothing ( No.1 ) |
- 日時： 2007/11/03 12:37
- 名前： あらし
- A number of steps are needed to evaluate v(2^1000)...
Note that, if k = p1^a1 · p2^a2 ·...· pr^ar, then (k) = (p1^a1 − p1^a1−1)·(p2^a2 − p2^a2−1)·...·(pr^ar − pr^ar−1). (1)
Show that:
φ(2k) = 2φ(k), if k is even;
φ(2k) = φ(k), if k is odd.
Let k be such that φ(k) = 2^m, for some m. Show that, if p is a prime that divides k, then p − 1 = φ(p) divides φ(k) = 2^m. Hence the primes that make up k are of the form 2^t + 1. (Note that if 2^t + 1 is prime then t is a power of 2.) Then use (1) to find all odd k such that φ(k) = 2m, for m < 32.
|
|
FAQ
RSS