2
$\begingroup$

Let $a,b\in\Bbb{N}\,|\,a+1=b$ and, $a$ and $b$ each have a prime number of factors

Question: how many pairs (a,b) satisfy these conditions?

I recommend trying this on your own first.

There is a thorough explanation on my progress on the problem. If you don't want to read that and just want to skip to the part of the problem that I am unable to solve you can scroll to the bottom of this page where I lay out the problem in it's final form along with the pairs i have found already.

The number of factors a number has is related to it's prime factorization.

If $c=p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}... p_k^{e_k}$ where $p_i$ is a prime and $e_i \in \Bbb{N}$, then the number of factors of $c$ is $(e_1+1)(e_2+1)(e_3+1)...(e_k+1)$. The only way for this product to be a prime is if there is only one $p_i$ and $e_i=p-1$ for some prime p. Therefore $a=p_1^{p_2-1}$ and $b=p_3^{p_4-1}$. The problem then is to find all solutions to the equation $p_1^{p_2-1}+1=p_3^{p_4-1}$. Since $a$ and $b$ differ by one. They have opposite parities so exactly one of them is even. This means there are two cases:$$p_1^{p_2-1}+1=2^{p_4-1}\qquad\qquad 2^{p_2-1}+1=p_3^{p_4-1}$$ Case 1 : $p_1^{p_2-1}+1=2^{p_4-1}$ $$\\$$ $p_1^{p_2-1}=2^{p_4-1}-1\quad$(1)$$\\$$ if $p_4=2$ then the right hand side (rhs) of (1) equals 1, however the left hand side (lhs) can't equal 1. therefore $p_4$ is odd. $\exists\,x\in\Bbb{N}\,|\,2x=p_4-1$ $$\\$$ $p_1^{p_2-1}=2^{2x}-1\quad$ (2) $$\\$$ $3|2^{2x}-1$ therefore $p_1=3$. The expression $2^{2x}-1$ can be factored into $(2^x-1)(2^x+1)$. $$\\$$ $3\,|\,(2^x-1)\quad$ xor $\quad 3\,|\,(2^x+1)$ the only prime factor of the lhs of (2) is three so the rhs can't have any other prime factors. The only possibility then is $2^x-1=1$ and $2^x+1=3$ so the first solution is $(3,4)$.$$\\$$ Case 2 : $2^{p_2-1}+1=p_3^{p_4-1}$ $$\\$$ Case 2a : $p_4$ is odd. $\exists\, y\in\Bbb{N}\,|\,2y=p_4-1$ $$\\$$ $2^{p_2-1}=p_3^{2y}-1\quad$(3)$$\\$$ $p_3^{2y}-1$ can be factored into $(p_3^{y}-1)(p_3^{y}+1)$ $$\\$$ $2\,|\,(p_3^{y}-1)\quad$and$\quad2\,|\,(p_3^{y}+1)\quad$ also, $\quad4\,|\,(p_3^{y}-1)\quad$xor$\quad4\,|\,(p_3^{y}+1)\quad$ $$\\$$ similarly to the first case the only prime factor on the lhs of (3) is two so the rhs can't be divisible by any other prime factors. The only possibility is $(p_3^{y}-1)=2$ and $(p_3^{y}+1)=4$. This results in the pair (8,9) but 8 doesn't have a prime number of factors therefore this isn't a solution.$$\\$$ case 2b: $p_4=2\quad\rightarrow\quad2^{p_2-1}+1=p_3 \quad$ (4) $$\\$$ If $(p_2-1)$ has an odd prime factor then $2^{p_2-1}+1$ can be factored. let $d\cdot f=p_2-1$ where $d$ is odd number (other than 1) then $$2^{d\cdot f}+1=(2^f+1)(2^{f\cdot(d-1)}-2^{f\cdot(d-2)}+2^{f\cdot(d-3)}-2^{f(d-4)}...+2^{2f}-2^f+1)$$. For example if $p_2-1=10$ then $(2^{10}+1)=(2^2+1)(2^8-2^6+2^4-2^2+1)$.The rhs of (4) is prime so $(p_2-1)$ can’t have an odd prime factor. This implies the only odd number $(p_2-1)$ can be is one. $(p_2-1)=1$ results in the second solution (2,3). Otherwise $(p_2-1)$ must be a power of two. $\exists \,m \in \Bbb{N}\,|\,(p_2-1)=2^m \rightarrow 2^m+1=p_2$. The same argument that was used to show $p_2-1$ is a power of two can be used to show $m$ is a power of two.$$\exists\, n \in \Bbb{N}\,|\qquad2^{2^n}+1=p_2\quad and \quad2^{2^{2^n}}+1=p_3 $$ so the problem boils down to for what values of n makes the two exponential expressions directly above both prime simultaneously? Plugging in 0,1,2 for n gives three more solutions (4,5) (16,17) (65536,65537) respectively $$\\$$ This is where I got stuck I don’t know if there are any more solutions or how to prove there aren’t any more solutions. Numbers of the form of $2^{2^n}+1$ are called fermat numbers. There are only five known fermat numbers that are prime (3,5,17,255,65537). Finding all fermat primes seems to be a very challenging problem but I’m hoping that since this a subset of the problem that this might actually be doable.

Bonus fact: Gauss proved that all N sided polygons that can drawn using a ruler and compass if and only if $\phi(N)=2^a$ where $\phi()$ is the totient function. N can be a power of two times the product of different fermat primes.

The problem in it’s final form:

$$2^{2^{2^n}}+1\qquad2^{2^n}+1$$

for what values of $n$ are both of the above expressions prime simultaneously (other than 0,1,2)? The pairs I have found for a and b are (2,3)(3,4)(4,5)(16,17)(65536,65537)

$\endgroup$
  • 1
    $\begingroup$ The primes of the form $2^{2^n}+1$ are called Fermat Primes. $65537$ is the largest known such prime and it is conjectured that no more Fermat Primes exists. $\endgroup$ – didgogns May 27 '18 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.