Kleines Matheproblem Rechnen mit Kongruenzen #4345325

    • Sportbernd
      Sportbernd
      Bronze
      Dabei seit: 18.01.2005 Beiträge: 22.572
      Nen freund und ich haben ein kleines Matheproblem, wir sind über jede Hilfe dankbar. Bitte nicht nur das Ergebnis sondern was dahintersteckt wäre toll.

      LG Sportbernd

      Aufgabe:

      Ist die Zahl 2^340 -1 durch 341 teilbar?
      Benutzen Sie das Rechnen mit Kongruenzen
  • 2 Antworten
    • crt32
      crt32
      Bronze
      Dabei seit: 17.02.2007 Beiträge: 15.895
      die aufgabe löst man jedenfalls so, dass man sich die Restklassen modulo 341 anschaut.
      Weiß nicht, ob ich mich verrechnet habe, aber

      2^340 = (2^10)^34 = 1024^34
      und 1024 = 1+ 3*341, also 1024 ≡ 1.

      dh 2^340 - 1 ≡ 1^34 - 1 = 0 ≡ 0 (mod 341)

      also ja ist teilbar.

      Du musst dir halt irgendwie sinnvoll überlegen, in welcher Restklasse 2^340 liegt, also einfach ausprobieren, mehr kann man dazu denke ich nicht großartig sagen.

      Oder ist das Problem eher dass du keine Ahnung von Restklassen usw hast?
    • Sportbernd
      Sportbernd
      Bronze
      Dabei seit: 18.01.2005 Beiträge: 22.572
      ne das reicht schon, herzlichen dank