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
be a positive integer. Show that there are infinitely many perfect squares of the form 
where 
is a positive integer.
then there are infinitely many perfect squares. We proceed with induction on 
we have 
Suppose that the result holds for some 
Then we have 
for some 
If 
we try to find 
such that 
It is clear that such a 
which has roots, such as 
Our induction is complete. Therefore, the result holds for all 
and 
such that 
divides 
for every natural n.
if there exists a 
such that 
or equivalently, if 
is a quadratic residue mod 
then we can find a 
Additionally, it is clear that if 
and 
then it is a quadratic residue of 
It claim that this is true for all 
In fact, we can generalize this to all primes 
not just 
Clearly, 
We now prove the stronger statement that 
We proceed by induction on 
Assume that it holds for some 
for some 
we find 
Let 
Then we have 
or 
Since we can obviously find such an 
distinct positive integers that has sum greater than 
distinct positive integers be 
in increasing order. Since the integers are distinct,![\[\frac{N}{2} \ge \sum_{i=k+2}^{2k+1} a_i \ge \sum_{i=1}^{k-1} a_i + k(k+1).\]](http://latex.artofproblemsolving.com/8/7/e/87ebe69eb8190c5c680858b672a33e1b8e7741f2.png)
![\[ a_{k+1} + \sum_{i=k+2}^{2k+1} a_i + \sum_{i=1}^{k-1} a_i > N.\]](http://latex.artofproblemsolving.com/a/5/b/a5bad43fdda9af81f53e350e3b302c481b7f1cad.png)
or 
Hence,![\[N \ge 2\sum_{i=k+2}^{2k+1} a_i \ge \sum_{i=1}^{k} (a_{k+1}+i) \ge 2k^3+3k^2+3k.\]](http://latex.artofproblemsolving.com/b/3/f/b3f5fad280ddaadb796ab194217a6706a8b7af8f.png)
We are done.
Compare max subset of 
where ![\[
S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q(q+1)(q+2)}
\]](http://latex.artofproblemsolving.com/c/0/b/c0bf0826fbe8897ebaf0d4b3c861120d502baefd.png)
Prove that if 
for integers 
and 
is divisible by 
we have![\[\frac{2}{(k-1)(k)(k+1)}=\frac{1}{k-1}-\frac{2}{k}+\frac{1}{k+1}=\frac{1}{k-1}+\frac{1}{k}+\frac{1}{k+1}-\frac{3}{k}.
\]](http://latex.artofproblemsolving.com/f/5/a/f5afa1d2c839b44c5f903dea7b72dd0ad8a8de28.png)
![\[2S_q=\sum_{i=2}^{\frac{3p-1}{2}} \frac{1}{i} - \sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i}=\sum_{i=\frac{p+1}{2}}^{\frac{3p-1}{2}}-1.\]](http://latex.artofproblemsolving.com/3/8/d/38decc6baecc8d7f07bc19f9abedff25ddda7fc5.png)
![\[\frac{1}{p}-2S_q= 1+\frac{1}{p}-\sum_{i=\frac{p+1}{2}}^{\frac{3p-1}{2}}.\]](http://latex.artofproblemsolving.com/d/8/c/d8ca41ea8f8b43a60aaaefa002c44887f5d1740a.png)
![\[\frac{m-n}{n}=\frac{1}{p}-2S_q-1= \frac{1}{p}-\sum_{i=\frac{p+1}{2}}^{\frac{3p-1}{2}}
\]](http://latex.artofproblemsolving.com/f/e/c/fec4a69412e504bcad74e9e36acb95536492601f.png)
![\[=-\left(\frac{1}{\frac{p+1}{2}}+\frac{1}{\frac{p+3}{2}} + \cdots + \frac{1}{p-1}+\frac{1}{p+1}+ \cdots \frac{1}{\frac{3p-1}{2}}\right).\]](http://latex.artofproblemsolving.com/c/7/6/c764e49bfefb8cc4494e9add3fc27b14169df104.png)
![\[\sum_{i=\frac{p+1}{2}}^{p-1} \frac{P}{i} + \sum_{i=p+1}^{\frac{3p-1}{2}} \frac{P}{i} = \sum_{j=1}^{\frac{p-1}{2}} \frac{P}{p-j} + \frac{p+j},\]](http://latex.artofproblemsolving.com/6/6/f/66f12de4eb3f043b4dc6ca293aa567fab30f1689.png)
This sum is clearly 
so 
is a multiple of 
March 2014
October 2013