Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Zsigmondy's Theorem"

(Created page with "{{stub}} '''Zsigmondy's Theorem''' states that, for positive relatively prime integers <math>a</math>, <math>b</math>, and <math>n</math> with <math>a>b</math>, there exi...")
 
m (Formatting)
 
Line 1: Line 1:
−
{{stub}}
+
'''Zsigmondy's Theorem''' states that, for positive [[relatively prime]] integers <math>a</math>, <math>b</math>, and <math>n</math> with <math>a>b</math>, there exists a prime number <math>p</math> (called a ''primitive prime factor'') such that <math>p|(a^n-b^n)</math> but <math>p\not|(a^k-b^k)</math> for all positive integers <math>k<n</math> EXCEPT (i) if <math>n=a-b=1</math>, (ii) if <math>n=2</math> and <math>a+b</math> is a power of <math>2</math>, or (iii) if <math>n=6</math>, <math>a=2</math>, and <math>b=1</math>. This theorem can sometimes be used to prove that no more solutions exist to [[Diophantine equations]].
  
−
'''Zsigmondy's Theorem''' states that, for positive [[relatively prime]] integers <math>a</math>, <math>b</math>, and <math>n</math> with <math>a>b</math>, there exists a prime number <math>p</math> (called a <math>\textit{primitive prime factor}</math>) such that <math>p</math> <math>|(a^n-b^n)</math> but <math>p\not|(a^k-b^k)</math> for all positive integers <math>k<n</math> EXCEPT (i) if <math>n=a-b=1</math>, (ii) if <math>n=2</math> and <math>a+b</math> is a power of <math>2</math>, or (iii) if <math>n=6</math>, <math>a=2</math>, and <math>b=1</math>. This theorem can sometimes be used to prove that no more solutions exist to [[Diophantine equations]].
+
== Example ==
  
−
== Example ==
+
We desire to find all solutions <math>(x,y)</math> to the Diophantine <math>3^x-1=5^y</math>. We notice that the first integer <math>x</math> for which <math>5|3^x-1</math> is <math>x=4</math>, which produces <math>3^4-1=80\neq 5^y</math>. Now, by Zsigmondy's Theorem (the exceptions do not apply here), for any positive integers <math>n\geq 4</math>, there must exist a primitive prime factor for each of the terms <math>3^n-1^n.</math> However, the right hand side of the equation only contains prime factors of <math>5</math>, and so there are <math>\boxed{\text{no solutions}}</math> to this Diophantine equation.
−
We desire to find all solutions <math>(x,y)</math> to the Diophantine <math>3^x-1=5^y.</math> We notice that the first integer <math>x</math> for which <math>5|3^x-1</math> is <math>x=4</math>, which produces <math>3^4-1=80\neq 5^y</math>. Now, by Zsigmondy's Theorem (the exceptions do not apply here), for any positive integers <math>n\geq 4</math>, there must exist a primitive prime factor for each of the terms <math>3^n-1^n.</math> However, the right hand side of the equation only contains prime factors of <math>5</math>, and so there are <math>\boxed{\text{no solutions}}</math> to this Diophantine equation.
 
  
 
== Problems ==
 
== Problems ==
−
#Find all solutions <math>(x,y,z)</math> to the Diophantine equation <math>7^x-1=2\cdot3^y\cdot5^z</math>.
+
 
 +
* Find all solutions <math>(x,y,z)</math> to the Diophantine equation <math>7^x-1=2\cdot3^y\cdot5^z</math>.
  
 
== See Also ==
 
== See Also ==
 +
 
* [[Diophantine equations]]
 
* [[Diophantine equations]]
  
−
[[Category: Number theory]]
+
[[Category:Number theory]]
−
[[Category: Theorems]]
+
[[Category:Theorems]]
 +
{{stub}}

Latest revision as of 21:06, 11 March 2025

Zsigmondy's Theorem states that, for positive relatively prime integers $a$, $b$, and $n$ with $a>b$, there exists a prime number $p$ (called a primitive prime factor) such that $p|(a^n-b^n)$ but $p\not|(a^k-b^k)$ for all positive integers $k<n$ EXCEPT (i) if $n=a-b=1$, (ii) if $n=2$ and $a+b$ is a power of $2$, or (iii) if $n=6$, $a=2$, and $b=1$. This theorem can sometimes be used to prove that no more solutions exist to Diophantine equations.

Example

We desire to find all solutions $(x,y)$ to the Diophantine $3^x-1=5^y$. We notice that the first integer $x$ for which $5|3^x-1$ is $x=4$, which produces $3^4-1=80\neq 5^y$. Now, by Zsigmondy's Theorem (the exceptions do not apply here), for any positive integers $n\geq 4$, there must exist a primitive prime factor for each of the terms $3^n-1^n.$ However, the right hand side of the equation only contains prime factors of $5$, and so there are $\boxed{\text{no solutions}}$ to this Diophantine equation.

Problems

  • Find all solutions $(x,y,z)$ to the Diophantine equation $7^x-1=2\cdot3^y\cdot5^z$.

See Also

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Zsigmondy%27s_Theorem&oldid=244801"