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.