## Euler totient and powers of 2 minus 1

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Euler totient and powers of 2 minus 1

Hi,

Phi(n) is Euler totient of n

How to prove that :
n>1

gcd(Phi(2^n - 1),n)=n

Example :
n=8

2^8-1=256-1=255
Phi(255)=128=8*32
gcd(128,8)=8
2^7-1=127
Phi(127)=126=7*18
gcd(126,7)=7
It is maybe elementary I do not know.

Thanks for any clue
Last edited by Goahead52 on Wed Oct 28, 2015 4:58 pm UTC, edited 1 time in total.

Repeekthgil
Posts: 11
Joined: Wed Jan 30, 2013 6:02 pm UTC

### Re: Euler totient and powers of 2 minus 1

That's a neat function.

2^n-1 is related to mersenne primes, which certainly have an interesting GCD's

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Euler totient and powers of 2 minus 1

I`m sorry I forgot to tape Phi(n)
So it is gcd(Phi(2^n-1),n)=n

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Euler totient and powers of 2 minus 1

Repeekthgil wrote:That's a neat function.

2^n-1 is related to mersenne primes, which certainly have an interesting GCD's

Thank you.
Except that I do not assume that n is prime or 2^n-1 is prime too.
It works with any n>1

Flumble
Yes Man
Posts: 2082
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Euler totient and powers of 2 minus 1

Even better, it works with any base, not just any exponent.
n|φ(an-1) for any a and n > 1.

Here is a concise explanation using the multiplicative group of integers modulo an-1. (that I nearly understand)

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Euler totient and powers of 2 minus 1

Flumble wrote:Even better, it works with any base, not just any exponent.
n|φ(an-1) for any a and n > 1.

Here is a concise explanation using the multiplicative group of integers modulo an-1. (that I nearly understand)

Thanks a lot!

jaap
Posts: 2087
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Euler totient and powers of 2 minus 1

I was too slow, but here is my proof anyway:

Start with Euler's Theorem, which says that aphi(m) = 1 mod m for any coprime integers a and m.

For our purposes we choose a=2, and m=2n-1, which are obviously coprime.
So 2phi(m) = 1 mod 2n-1.

The multiplicative order of 2 in the group of integers mod 2n-1 is n. This is because obviously 2n = 1 mod 2n-1, and no smaller power of 2 can give 1 modulo 2n-1.

From 2phi(m) = 1 mod 2n-1, we can then conclude that phi(m) must be some multiple of the multiplicative order of 2. This is essentially a simple case of Lagrange's theorem applied to the group generated by 2.

In other words phi(2n-1) is a multiple of n.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Euler totient and powers of 2 minus 1

Thank you.
I have found that 2^n - 1 have always at least one divisor of the form a*n+1 (where a is positive integer > 1)
I could not explain it.
Now I understand why.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Euler totient and powers of 2 minus 1

2^7-1 is = 127 which is prime divisible by (7*18+1)
2^8-1 is = 255=3*5*17 which divisible by (8*2+1)
and so on

If we know that at least one of the factors of 2^n-1 could be expressed as (a*n)+1 then it will help factorizing 2^n-1

I need your thoughts before going forward.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Euler totient and powers of 2 minus 1

Assuming that for any 2^n-1 there is ALWAYS at least one prime divisor of the form a*p+1 we could add a new proof for the infinity of primes :

First statement :

If n is prime then we have 2 outcomes :
- either 2^n-1 is prime itself 2^n-1 then is bigger than n
- either 2^n-1 is composite and of its prime factor has the form of a*p+1 hence a*p+1 > n implying that that there is always an infinite number of primes

Second statement :
If n is prime then at least one of its prime divisors is of the form a*p+1 means that each prime could be paired with another bigger one
Than there are an infinite prime numbers "paired".

All those statement can be proved true using Euler theorem.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Euler totient and powers of 2 minus 1

Examples :

2^5-1=31 is prime> 5
2^7-1=127 is prime > 7
2^11-1=23*89 all primes 23 et 89 > 11
2^13-1=8191 is prime > 13

and so on