1. Was ist ´phi(8!)´?
  2. Wie viele Zahlen ´a´ gibt es, die teilerfremd zu ´111´ sind und für die ´22 <= a < 222´ gilt?
  3. Wenn ´t >= 1´ ein Teiler von ´m >= 1´ ist, wie viele Zahlen ´a´ mit ´0 <= a < m´ gibt es, für die ´gcd(a,m) = t´?
Approach

Teil 1

´8! = 2^(e_2) * 3^(e_3) * 5^(e_5) * 7^(e_7)´ ´e_2 = |__8/2__| + |__8/4__| + |__8/8__| = 4 + 2 + 1 = 7´ ´e_3 = |__8/3__| = 2´ ´e_5 = |__8/5__| = 1´ ´e_7 = |__8/7__| = 1´

´=> 8! = 2^7 * 3^2 * 5 * 7´

´phi(8!) = phi(2^7 * 3^2 * 5 * 7)´ ´= phi(2^7) * phi(3^2) * phi(5) * phi(7)´ ´= 2^6(2-1) * 3(3-1) * 4 * 6´ ´= 64 * 6 * 24´ ´= 9216´

Teil 2

Gesucht: Anzahl der Zahlen ´a´ mit ´22 <= a <= 222´ mit ´gcd(a,111) = 1´

´0,1,…,110´: ´phi(111)´ Zahlen sind teilerfremd zu ´111´ ´111,112,…,221´: ´phi(111)´ Zahlen sind teilerfremd zu ´111´

´=> 2 * phi(111) - b´ mit ´b´ gleich der Anzahl der Teilerfremden Zahlen in ´0,1,…,21´

´111 = 3 * 37´ ´=> phi(111) = 2 * 36 = 72´

´b = 22 - 2 (0 " und " 3 ) = 20´

´2 * 72 - 20 = 124´

Teil 3

´a = a_0 * t´ ´m = m_0 * t´

´gcd(a_0, m_0) = 1´

´0 <= a_0 t <= m_0 t´ ´0 <= a_0 <= m_0´

´=> a <= m/t´


Solution
    1. ´9216´
    2. ´124´
    3. ´a <= m/t´
  • URL:
  • Language:
  • Subjects: math
  • Type: Calculate
  • Duration: 30min
  • Credits: 3
  • Difficulty: 0.6
  • Tags: hpi divisor
  • Note:
    HPI, 2014-06-16, Mathe 2, Aufgabe 42
  • Created By: adius
  • Created At:
    2014-07-26 18:31:01 UTC
  • Last Modified:
    2014-07-27 20:48:16 UTC