Für alle n aus N sind n und 2n-1 teilerfremd.

Question

Aufgabe:

Beweisen oder widerlegen Sie: Für alle n aus N sind n und 2n-1 teilerfremd.

Problem/Ansatz:

Kann mir jemand erklären wie ich die oben genannte Aufgabe lösen kann?

!

Answer 1

Es sei m>0 Teiler von n, also

        n ≡ 0 mod m.

Dann ist auch

        2n ≡ 0 mod m.

Also ist

        2n-1 ≡ m-1 mod m.

Demnach ist m genau dann Teiler von 2n-1, wenn

        m-1 = 0

ist. Das ist nur dann der Fall, wenn

        m = 1

ist. Einziger positiver gemeinsamer Teiler von n und 2n-1 ist also 1. Das heißt, n und 2n-1 sind teilerfremd.