Zsigmondy's Theorem
by KingSmasher3, Oct 10, 2013, 3:02 AM
Continuing my NT adventures...
ISL 2000 N4: Find all triplets of positive integers
such that 
.
_______
From Zsigmondy's Theorem,
has a prime factor that is not a factor of 
unless 
and 
Hence, we see that the given statement holds only if 
with 
ISL 1997 #14: Let
be positive integers such that 
and 
Prove that if 
and 
have the same prime divisors, then 
is a power of 2.
_______
Without loss of generality, let
By Zsigmondy's Theorem, 
has a prime factor that is not a factor of 
unless 
or 
is a power of 
and 
We can check that the first case does not yield any possible value of 
so we are done.
MOP 2001: Find all quadruples of positive integers
such that 
is a prime number, 
and 
_______
Obviously
If
and 
is composite, then by Zsigmondy's theorem, 
cannot be a power of a prime. The only exception to this theorem occurs when 
which clearly does not work. Therefore, must be prime. We have 
implying that 
It follows that 
must be odd, so 
Thus, 
with 
Now we know that 
and 
so cannot be prime.
If
by Zsigmondy's theorem, cannot be a power of a prime. The only exception occurs when 
is a power of and 
Let 
Then 
or 
It is clear that this only holds when 
Hence, our only solution is
ISL 2002 N3: Let
be distinct primes greater than 
. Show that 
has at least 
divisors.
_______
Let
be the product of a subset of 
Then clearly, 
Now, let 
and 
Since there are 
possible values for 
by Zsigmondy's Theorem, 
has at least distinct prime factors, which means at least 
total factors. Note that the exceptional case 
does not occur because all primes 
are greater than 
Alternate Solution: We induct on
Clearly when 
has at least 
factors: 
Now given two integers 
with 
we have
![\[\gcd(2^a+1, 2^b+1) | \gcd(2^{2a}-1,2^{2b}-1) = 2^{\gcd(2a,2b)}-1 = 3.
\]](//latex.artofproblemsolving.com/4/c/9/4c9d18138f5f70da71a74b12c7c06f1aa63ab99e.png)
This can be seen by applying the Euclidean Algorithm. Furthermore, we can easily show that
is a multiple of but not 
if and only if 
We have 
and 
is a factor of and thus 
so by the two facts stated above, 
is a factor of 
and is relatively prime to 
It follows that 
has at least 
factors. It can be seen that 
so has at least factors (for every divisor 
we have 
) as desired.
ISL 2000 N4: Find all triplets of positive integers
such that 
._______
From Zsigmondy's Theorem,
has a prime factor that is not a factor of 
unless 
and 
Hence, we see that the given statement holds only if 
with 
ISL 1997 #14: Let
be positive integers such that 
and 
Prove that if 
and 
have the same prime divisors, then 
is a power of 2._______
Without loss of generality, let
By Zsigmondy's Theorem, 
has a prime factor that is not a factor of 
unless 
or 
is a power of 
and 
We can check that the first case does not yield any possible value of 
so we are done.MOP 2001: Find all quadruples of positive integers
such that 
is a prime number, 
and 
_______
Obviously
If
and 
is composite, then by Zsigmondy's theorem, 
cannot be a power of a prime. The only exception to this theorem occurs when 
which clearly does not work. Therefore, must be prime. We have 
implying that 
It follows that 
must be odd, so 
Thus, 
with 
Now we know that 
and 
so cannot be prime.If
by Zsigmondy's theorem, cannot be a power of a prime. The only exception occurs when 
is a power of and 
Let 
Then 
or 
It is clear that this only holds when 
Hence, our only solution is
ISL 2002 N3: Let
be distinct primes greater than 
. Show that 
has at least 
divisors._______
Let
be the product of a subset of 
Then clearly, 
Now, let 
and 
Since there are 
possible values for 
by Zsigmondy's Theorem, 
has at least distinct prime factors, which means at least 
total factors. Note that the exceptional case 
does not occur because all primes 
are greater than 
Alternate Solution: We induct on
Clearly when 
has at least 
factors: 
Now given two integers 
with 
we have![\[\gcd(2^a+1, 2^b+1) | \gcd(2^{2a}-1,2^{2b}-1) = 2^{\gcd(2a,2b)}-1 = 3.
\]](http://latex.artofproblemsolving.com/4/c/9/4c9d18138f5f70da71a74b12c7c06f1aa63ab99e.png)
This can be seen by applying the Euclidean Algorithm. Furthermore, we can easily show that
is a multiple of but not 
if and only if 
We have 
and 
is a factor of and thus 
so by the two facts stated above, 
is a factor of 
and is relatively prime to 
It follows that 
has at least 
factors. It can be seen that 
so has at least factors (for every divisor 
we have 
) as desired.This post has been edited 6 times. Last edited by KingSmasher3, Jan 5, 2014, 7:07 PM
March 2014
October 2013