Finde ein ´x in ZZ´ mit ´x -= 9717^1030 (mod 97)´ und ´0 <= x < 97´.

Approach

´x = 9717^1030 (mod 97)´ mit ´0 <= x < 97´ ´=> x -= 17^1030 (mod 97)´

´gcd(17,97) = 1´, ´phi(97) = 96´

´17^96 -= 1 (mod 97)´

´1030 = 96 * 10 + 70´ ´x -= 17^1030 -= 17^(96 * 10 + 70) -= (17^96)^10 * 17^70 -= 17^70 (mod 97)´

´70_10 = 1000110_2 = 2^1 + 2^2 + 2^6´

´17^70 = 17^(2 + 4 + 64)´

=> ´x -= 17^2 * 17^4 * 17^64´

´17^2 -= 289 -= 95 (mod 97)´ ´17^4 -= 95^2 -= 4 (mod 97)´ ´17^8 -= 4^2 -= 16 (mod 97)´ ´17^16 -= 16^2 -= 62 (mod 97)´ ´17^32 -= 62^2 -= 61 (mod 97)´ ´17^64 -= 61^2 -= 35 (mod 97)´

´x -= 95 * 4 * 35 -= 11 (mod 97)´


Solution

  • ´x -= 11 (mod 97)´

  • URL:
  • Language:
  • Subjects: math
  • Type: Calculate
  • Duration: 25min
  • Credits: 3
  • Difficulty: 0.6
  • Tags: hpi congruence modulo
  • Note:
    HPI, 2014-06-10, Mathe 2, Aufgabe 39
  • Created By: adius
  • Created At:
    2014-07-26 18:03:22 UTC
  • Last Modified:
    2014-07-26 18:03:22 UTC