Euler totient and powers of 2 minus 1

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Euler totient and powers of 2 minus 1

Postby Goahead52 » Wed Oct 28, 2015 3:59 pm UTC

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

Postby Repeekthgil » Wed Oct 28, 2015 4:43 pm UTC

That's a neat function.

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

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

Re: Euler totient and powers of 2 minus 1

Postby Goahead52 » Wed Oct 28, 2015 4:59 pm UTC

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

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

Re: Euler totient and powers of 2 minus 1

Postby Goahead52 » Wed Oct 28, 2015 5:26 pm UTC

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

User avatar
Flumble
Yes Man
Posts: 1996
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Euler totient and powers of 2 minus 1

Postby Flumble » Wed Oct 28, 2015 5:53 pm UTC

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)

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

Re: Euler totient and powers of 2 minus 1

Postby Goahead52 » Wed Oct 28, 2015 5:55 pm UTC

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!

User avatar
jaap
Posts: 2077
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Euler totient and powers of 2 minus 1

Postby jaap » Wed Oct 28, 2015 6:01 pm UTC

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.

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

Re: Euler totient and powers of 2 minus 1

Postby Goahead52 » Wed Oct 28, 2015 6:16 pm UTC

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.

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

Re: Euler totient and powers of 2 minus 1

Postby Goahead52 » Wed Oct 28, 2015 6:19 pm UTC

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.

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

Re: Euler totient and powers of 2 minus 1

Postby Goahead52 » Wed Oct 28, 2015 7:16 pm UTC

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.

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

Re: Euler totient and powers of 2 minus 1

Postby Goahead52 » Wed Oct 28, 2015 7:23 pm UTC

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


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests