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´\n´=> x -= 17^1030 (mod 97)´\n\n´gcd(17,97) = 1´, ´phi(97) = 96´\n\n´17^96 -= 1 (mod 97)´\n\n´1030 = 96 \* 10 + 70´\n´x -= 17^1030 -= 17^(96 \* 10 + 70) -= (17^96)^10 \* 17^70 -= 17^70 (mod 97)´\n\n´70_10 = 1000110_2 = 2^1 + 2^2 + 2^6´\n\n´17^70 = 17^(2 + 4 + 64)´\n\n=> ´x -= 17^2 \* 17^4 \* 17^64´\n\n´17^2 -= 289 -= 95 (mod 97)´\n´17^4 -= 95^2 -= 4 (mod 97)´\n´17^8 -= 4^2 -= 16 (mod 97)´\n´17^16 -= 16^2 -= 62 (mod 97)´\n´17^32 -= 62^2 -= 61 (mod 97)´\n´17^64 -= 61^2 -= 35 (mod 97)´\n\n´x -= 95 \* 4 \* 35 -= 11 (mod 97)´"


Solution

  • ´x -= 11 (mod 97)´

  • URL:
  • Language: Deutsch
  • 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: ad-si
  • Created At:
    2014-07-26 18:03:22 UTC
  • Last Modified:
    2014-07-26 18:03:22 UTC