JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

Integers II. Euler's totient.

Image 

The Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. In other words, φ(1) = 1, and for any n ∈ ℤ, n > 1, φ(n) is the number of positive integers a less than n (a ≤ n) and relative prime to n, (a, n) = 1, e.g., φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2, φ(7) = 6, φ(8) = 4.

n 1 2 3 4 5 6 7 8 9 10 11 12
φ(n) 1 1 2 2 4 2 6 4 6 4 10 4

The Euler φ-function is a map φ:ℤ+ → ℝ such that φ(1) = 1 and φ(n) is equal to the number of positive integers coprime to n for n > 1.

Properties

Applications

The Method of Repeated Squares

What is 57 mod 21 or 271321 (mod 481)?

The first step is to write the exponent in binary. Of course, every number a can be written as the sum of distinct power of 2, a = 2k1 + 2k2 + … + 2kn, e.g., 710 = 1112 and 32110= 1010000012.

The laws of exponents still work in ℤn [b≡ax (mod n), c≡ay (mod n) ⇒ bc≡ax+y (mod n),] so we can calculate a2k (mod n) in k multiplications by computing a20 (mod n), a21 (mod n), …, a2k (mod n)

57 mod 21 ≡ 54+2+1 mod 21

  1. 51 = 5 mod 21 = 5
  2. 52 = 25 ≡ 4 mod 21
  3. 54 = (52)2 ≡ [It’s time to use the previous one] 42 ≡ 16 mod 21.

Finally, let’s combine our partial results, 57 mod 21 ≡ 54+2+1 mod 21 ≡ 16·4·5 mod 21 ≡ 320 mod 21 ≡ 5 mod 21.

Analogously, but we will need a little more extra effort, 27120+26+28 ≡ 27120· 27126· 27128 (mod 481)

  1. 27120 ≡ 271 (mod 481)
  2. 27121 ≡ 73441 (mod 481) ≡ 329 (mod 481)
  3. 27122 ≡ [Using the previous result] 3292 ≡ 108241 ≡ 16 (mod 481).
  4. 27123 ≡ 162 ≡ 256 (mod 481).
  5. 27124 ≡ 2562 ≡ 120 (mod 481).
  6. 27125 ≡ 1202 ≡ 451 (mod 481).
  7. 27126 ≡ 4512 ≡ 419 (mod 481).
  8. 27127 ≡ 4192 ≡ 477 (mod 481).
  9. 27128 ≡ 4772 ≡ 16 (mod 481).

Finally, let’s combine our partial results, 27120+26+28 ≡ 27120· 27126· 27128 (mod 481) ≡ 271·419·16 ≡ 47 (mod 481).

Bitcoin donation

JustToThePoint Copyright © 2011 - 2024 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun. Social Issues, Join us.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.