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^81=2561=255
Phi(255)=128=8*32
gcd(128,8)=8
2^71=127
Phi(127)=126=7*18
gcd(126,7)=7
It is maybe elementary I do not know.
Thanks for any clue
Euler totient and powers of 2 minus 1
Moderators: gmalivuk, Moderators General, Prelates
Euler totient and powers of 2 minus 1
Last edited by Goahead52 on Wed Oct 28, 2015 4:58 pm UTC, edited 1 time in total.

 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^n1 is related to mersenne primes, which certainly have an interesting GCD's
2^n1 is related to mersenne primes, which certainly have an interesting GCD's
Re: Euler totient and powers of 2 minus 1
I`m sorry I forgot to tape Phi(n)
So it is gcd(Phi(2^n1),n)=n
So it is gcd(Phi(2^n1),n)=n
Re: Euler totient and powers of 2 minus 1
Repeekthgil wrote:That's a neat function.
2^n1 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^n1 is prime too.
It works with any n>1
Re: Euler totient and powers of 2 minus 1
Even better, it works with any base, not just any exponent.
nφ(a^{n}1) for any a and n > 1.
Here is a concise explanation using the multiplicative group of integers modulo a^{n}1. (that I nearly understand)
nφ(a^{n}1) for any a and n > 1.
Here is a concise explanation using the multiplicative group of integers modulo a^{n}1. (that I nearly understand)
Re: Euler totient and powers of 2 minus 1
Flumble wrote:Even better, it works with any base, not just any exponent.
nφ(a^{n}1) for any a and n > 1.
Here is a concise explanation using the multiplicative group of integers modulo a^{n}1. (that I nearly understand)
Thanks a lot!
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 a^{phi(m)} = 1 mod m for any coprime integers a and m.
For our purposes we choose a=2, and m=2^{n}1, which are obviously coprime.
So 2^{phi(m)} = 1 mod 2^{n}1.
The multiplicative order of 2 in the group of integers mod 2^{n}1 is n. This is because obviously 2^{n} = 1 mod 2^{n}1, and no smaller power of 2 can give 1 modulo 2^{n}1.
From 2^{phi(m)} = 1 mod 2^{n}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(2^{n}1) is a multiple of n.
Start with Euler's Theorem, which says that a^{phi(m)} = 1 mod m for any coprime integers a and m.
For our purposes we choose a=2, and m=2^{n}1, which are obviously coprime.
So 2^{phi(m)} = 1 mod 2^{n}1.
The multiplicative order of 2 in the group of integers mod 2^{n}1 is n. This is because obviously 2^{n} = 1 mod 2^{n}1, and no smaller power of 2 can give 1 modulo 2^{n}1.
From 2^{phi(m)} = 1 mod 2^{n}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(2^{n}1) is a multiple of n.
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.
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.
Re: Euler totient and powers of 2 minus 1
2^71 is = 127 which is prime divisible by (7*18+1)
2^81 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^n1 could be expressed as (a*n)+1 then it will help factorizing 2^n1
I need your thoughts before going forward.
2^81 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^n1 could be expressed as (a*n)+1 then it will help factorizing 2^n1
I need your thoughts before going forward.
Re: Euler totient and powers of 2 minus 1
Assuming that for any 2^n1 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^n1 is prime itself 2^n1 then is bigger than n
 either 2^n1 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.
First statement :
If n is prime then we have 2 outcomes :
 either 2^n1 is prime itself 2^n1 then is bigger than n
 either 2^n1 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.
Re: Euler totient and powers of 2 minus 1
Examples :
2^51=31 is prime> 5
2^71=127 is prime > 7
2^111=23*89 all primes 23 et 89 > 11
2^131=8191 is prime > 13
and so on
2^51=31 is prime> 5
2^71=127 is prime > 7
2^111=23*89 all primes 23 et 89 > 11
2^131=8191 is prime > 13
and so on
Who is online
Users browsing this forum: No registered users and 11 guests