Find the smallest prime number $p$ that cannot be represented in the form $|3^{a} - 2^{b}|$, where $a$ and $b$ are non-negative integers.
Problem
Source: China TST 1995, problem 1
Tags: modular arithmetic, number theory
Pascual2005
18.05.2005 03:32
I think it is $17$, however I havent checked all the cases, what one should try is to look what pairs $(a,b)$ modulo 16, give $3^a-2^b$ a multiple of 17, and show using factorizations, modulo 5, modulo 11, modulo 16, or more, to show they have more factors or the equivalence is not truth!
Peter Scholze
04.12.2005 11:32
17=81-64... however, it looks like 37 does not work. The idea to prove it should be the same, still.
Flatter
04.12.2005 12:52
$37=|27-64|$ However, I can prove that 41 cannot be represented in form $|3^{a}-2^{b}|$
Let's suppose that $41=|3^{a}-2^{b}|$ then:
a) $41=3^{a}-2^{b}$
$2^{b}\equiv1(mod3)$
$b=2k$
If $b=0$ then $42=3^{a}$, which is impossible, so $b\geq 2$
$3^{a}\equiv1(mod4)$
$a=2l$
If $a=0$ then $41=3^{a}-2^{b}=1-2^{b}<0$, which is impossible, so $a\geq 2$
$41=3^{2l}-2^{2k}=(3^{l}-2^{k})(3^{l}+2{k})$
$3^{l}+2^{k}>3^{l}-2^{k}>0$, so $3^{l}+2^{k}=41$ and $3^{l}-2^{k}=1$
From there we get $3^{l}=21$ and $2^{k}=20$, which is impossible.
b) $41=2^{b}-3^{a}$
$2^{b}>2^{b}-3^{a}=41$, so $b>5$,and $2^{b}\equiv0(mod8)$
And so $3^{a}\equiv(-1)(mod8)$, which is impossible.
da-kid
17.09.2007 02:32
I think it's 3. For it to be 3, 2^b would need to be a multiple of 3. You can factor out a 3 from 3^a making it 3^(a-1) * 3. To get 3, 2^b would need to become (3^(a-1) +/-1) * 3 and because 2^b is not a multiple of 3, this could never occur.
scorpius119
17.09.2007 03:05
da-kid wrote: I think it's 3. For it to be 3, 2^b would need to be a multiple of 3. You can factor out a 3 from 3^a making it 3^(a-1) * 3. To get 3, 2^b would need to become (3^(a-1) +/-1) * 3 and because 2^b is not a multiple of 3, this could never occur. Be careful! The nonnegative integers include 0, so $ 3=|3^{0}-2^{2}|$ can be represented.
FINNN
26.05.2014 03:33
This is not a comment.
va2010
26.05.2014 04:01
Yes. |2^5-3^1|
mathtastic
13.08.2014 06:09
We claim that the smallest prime that cannot be written in the given form is $41$. It's easy to verify that all primes under $41$ can be written in the given form.
Case 1: $3^a-2^b=41$.
It is clear that $a\ge 1$, so we can safely say that $3^a\equiv 0\pmod{3}$. From here we can take $\pmod{3}$ to get that $-2^b\equiv 41\equiv 2\pmod{3}\implies 2^b\equiv 1\pmod{3}$. Checking values of $2^b\pmod{3}$ we see that $2^b\equiv 1\pmod{3}\iff b\equiv 0\pmod{2}$. Thus we can set $b=2k\implies 2^b=2^{2k}=(2^k)^2$. Let's leave this aside for now and go back to our original equation. It is clear that $b\ge 2$, so we can safely say that $2^b\equiv 0\pmod{4}$. From here we can take $\pmod{4}$ to get that $3^a\equiv 41\equiv 1\pmod{4}$. Checking values of $3^a\pmod{4}$ we see that $3^a\equiv 1\pmod{4}\iff a\equiv 0\pmod{2}$. Thus we can set $a=2j\implies 3^a=3^{2j}=(3^j)^2$. Now we can see where we're getting. We have $(3^j)^2-(2^k)^2=41\implies (3^j-2^k)(3^j+2^k)=41$. Clearly, since $41$ is prime and $3^j+2^k\not=1$, we must have $3^j-2^k=1$ and $3^j+2^k=41$. Adding these equations and dividing by $2$ gives $3^j=21$ which clearly isn't possible. Thus this case has no solutions. $\square$
Case 2: $2^b-3^a=41$.
It is clear that $a\ge 1$, so we can safely say that $3^a\equiv 0\pmod{3}$. From here we can take $\pmod{3}$ to get that $2^b\equiv 41\equiv 2\pmod{3}$. Checking values of $2^b \pmod{3}$ we see that $2^b\equiv 2\pmod{3}\iff b\equiv 1\pmod{2}$. This will be important later, so keep it in mind. It is clear that $b\ge 2$, so we can safely say that $2^b\equiv 0\pmod{4}$. From here we can take $\pmod{4}$ to get that $-3^a\equiv 41\equiv 1\pmod{4}\implies 3^a\equiv 3\pmod{4}$. Checking values of $3^a\pmod{4}$ we see that $3^a\equiv 3\pmod{4}\iff a\equiv 1\pmod{2}$. Since we still aren't done, let's try another mod. Let's try $8$. We have $2^b-3^a\equiv 1\pmod{8}$. Values of $2^b\pmod{8}$ are $1,2,4,0,0,0,\cdots$. Values of $3^a\pmod{8}$ are $1,3,1,3,1,3,\cdots$. However, since we know that $a\equiv 1\pmod{2}$ we must have $3^a\equiv 3\pmod{8}$. Thus we now have $2^a-3\equiv 1\pmod{8}\implies 2^a\equiv 4\pmod{8}\implies a=2$. However, $a=2$ won't work because we have $a\equiv 1\pmod{2}$. Thus this case also has no solutions. $\square$
Since we have exhausted both cases, we are done (whew!)
$\mathbb{Q}.\mathbb{E}.\mathbb{D}.$
FINNN
14.08.2014 17:21
Sorry everybody
AkshajK
14.08.2014 17:27
Actually it is pretty easy to show that it is the smallest because \begin{eqnarray*} 37&=& 64 - 27\\31&=& 32 - 1\\29&=& 32 - 3\\23&=& 32 - 9\\19&=& 27 - 8\\17&=& 81 - 64\\13&=& 16 - 3\\11&=& 27-16\\7&=& 16-9\\5&=& 9-4\\3&=& 4-1\\2&=& 3-1 \end{eqnarray*}
mathtastic
14.08.2014 18:14
FINNN wrote: Hey mathtastic, now that you no longer have a nice list of solutions for $p<41$, I see you've "made a claim". Unfortunately, if you were to submit this proof for an olympiad asking "what is the smallest", you would get perhaps 50% of the possible points. Proving something to be a solution is quite trivial compared to showing that it is the smallest. You'll have to rethink your proof. Why don't you try the problem yourself? AkshajK just showed how simple it is to make all of the smaller primes. With 41 you get stuck so make a claim and prove it. It isn't trivial to prove but it is trivial to verify all smaller primes work.
JuanOrtiz
09.06.2015 05:01
Notice that $b=5$ $a=2(log_3(i)+1)$ proves that $41$ is indeed possible!
mishai
09.06.2015 08:19
a and b are non-negative integers, not complex numbers.
Alex314159
04.03.2021 03:57
AkshajK wrote: Actually it is pretty easy to show that it is the smallest because \begin{eqnarray*} 37&=& 64 - 27\\31&=& 32 - 1\\29&=& 32 - 3\\23&=& 32 - 9\\19&=& 27 - 8\\17&=& 81 - 64\\13&=& 16 - 3\\11&=& 27-16\\7&=& 16-9\\5&=& 9-4\\3&=& 4-1\\2&=& 3-1 \end{eqnarray*} Hi! We need to show that 41 is the smallest value of $p$ satisfying the condition. Suppose that $|3^a-2^b|=41$ So we have two cases: 1) $3^a-2^b=-41$. \begin{align*} 2^b-3^a&=41\\ 2^b-3^a&=2^5+3^2\\ 2^b-2^5&=3^a+3^2>0 \end{align*} So, $b>5$. That implies $32|3^a+3^2$. Thus $8|3^a+3^2$, wich is equivalent to $3^a+3^2\equiv 0\mod 8$. But \begin{align*} 3^a+3^2&\equiv 0\mod 8\\ \iff 3^a&\equiv -3^2\mod 8\\ \iff 3^a&\equiv 7 \mod 8 \end{align*} And the last equation is false, because $3^{a}\equiv 1\mod 8\lor 3^{a}\equiv 3\mod 8$. 2)$3^a-2^b=41$ \begin{align*} 3^a-2^b&=41\\ 3^a-2^b&=2^5+3^2\\ 3^a-3^2&=2^b+2^5>0 \end{align*} So, $a>2$. That implies $9|2^b+2^5$, wich is equivalent to $2^b+2^5\equiv 0\mod 9$. It's easy to see that this only happens when $b=6k+2$ for some integer $k$ (because $2^6\equiv 1\mod 9$). Finally: \begin{align*} 3^a-3^2&\equiv 2^5+2^b \mod 13\\ \iff 3^a&\equiv 3^2+2^5+\left(2^6\right)^k 2^2\mod 13\\ \iff 3^a&\equiv 9+6+\left(1\right)^k 4\mod 13\\ \iff 3^a&\equiv 6\mod 13 \end{align*} And the last equation is false, because $3^{a}\equiv 1\mod 13\lor 3^{a}\equiv 3\mod 13\lor3^{a}\equiv 9\mod 13$. Sorry if my english is not perfect.... Please tell me if I am wrong.
Alex314159
04.03.2021 05:01
mathtastic wrote:
We claim that the smallest prime that cannot be written in the given form is $41$. It's easy to verify that all primes under $41$ can be written in the given form.
Case 1: $3^a-2^b=41$.
It is clear that $a\ge 1$, so we can safely say that $3^a\equiv 0\pmod{3}$. From here we can take $\pmod{3}$ to get that $-2^b\equiv 41\equiv 2\pmod{3}\implies 2^b\equiv 1\pmod{3}$. Checking values of $2^b\pmod{3}$ we see that $2^b\equiv 1\pmod{3}\iff b\equiv 0\pmod{2}$. Thus we can set $b=2k\implies 2^b=2^{2k}=(2^k)^2$. Let's leave this aside for now and go back to our original equation. It is clear that $b\ge 2$, so we can safely say that $2^b\equiv 0\pmod{4}$. From here we can take $\pmod{4}$ to get that $3^a\equiv 41\equiv 1\pmod{4}$. Checking values of $3^a\pmod{4}$ we see that $3^a\equiv 1\pmod{4}\iff a\equiv 0\pmod{2}$. Thus we can set $a=2j\implies 3^a=3^{2j}=(3^j)^2$. Now we can see where we're getting. We have $(3^j)^2-(2^k)^2=41\implies (3^j-2^k)(3^j+2^k)=41$. Clearly, since $41$ is prime and $3^j+2^k\not=1$, we must have $3^j-2^k=1$ and $3^j+2^k=41$. Adding these equations and dividing by $2$ gives $3^j=21$ which clearly isn't possible. Thus this case has no solutions. $\square$
Case 2: $2^b-3^a=41$.
It is clear that $a\ge 1$, so we can safely say that $3^a\equiv 0\pmod{3}$. From here we can take $\pmod{3}$ to get that $2^b\equiv 41\equiv 2\pmod{3}$. Checking values of $2^b \pmod{3}$ we see that $2^b\equiv 2\pmod{3}\iff b\equiv 1\pmod{2}$. This will be important later, so keep it in mind. It is clear that $b\ge 2$, so we can safely say that $2^b\equiv 0\pmod{4}$. From here we can take $\pmod{4}$ to get that $-3^a\equiv 41\equiv 1\pmod{4}\implies 3^a\equiv 3\pmod{4}$. Checking values of $3^a\pmod{4}$ we see that $3^a\equiv 3\pmod{4}\iff a\equiv 1\pmod{2}$. Since we still aren't done, let's try another mod. Let's try $8$. We have $2^b-3^a\equiv 1\pmod{8}$. Values of $2^b\pmod{8}$ are $1,2,4,0,0,0,\cdots$. Values of $3^a\pmod{8}$ are $1,3,1,3,1,3,\cdots$. However, since we know that $a\equiv 1\pmod{2}$ we must have $3^a\equiv 3\pmod{8}$. Thus we now have $2^a-3\equiv 1\pmod{8}\implies 2^a\equiv 4\pmod{8}\implies a=2$. However, $a=2$ won't work because we have $a\equiv 1\pmod{2}$. Thus this case also has no solutions. $\square$
Since we have exhausted both cases, we are done (whew!)
$\mathbb{Q}.\mathbb{E}.\mathbb{D}.$
Amazing solution!
i3435
04.03.2021 05:58
"Try this problem, it's a better one out of the oly problems on the handout"- Math Circle *Some time later* "I finished the problem, can you go over it at the end"-me "Lol you did that dumb problem"- Math Circle
We can show that all of the primes below $41$ are possible.
$2=|3^1-2^0|$
$3=|3^0-2^2|$
$5=|3^1-2^2|$
$7=|3^0-2^3|$
$11=|3^3-2^4|$
$13=|3^1-2^4|$
$17=|3^4-2^6|$
$19=|3^3-2^3|$
$23=|3^3-2^2|$
$29=|3^1-2^5|$
$31=|3^0-2^5|$
$37=|3^3-2^6|$
Now we can show that $41$ is the answer.
Case 1: $2^b-3^a=41$
$3^a\equiv 1,3\mod 8$, so $2^b\equiv 2,4\mod 8$. This means $b=1,2$, which is impossible.
Case 2: $3^a-2^b=41$
$3^a\equiv 1,3\mod 8$, so $2^b\equiv 0,2\mod 8$. $b=1$ doesn't work, so $2^b\equiv 0\mod 8$ and $3^a\equiv 1\mod 8$. Thus $a$ is even. $2^b\equiv 1\mod 3$, so $b$ is also even. Then let $3^a=x^2$ and $2^b=y^2$. If $x^2-y^2=41$, then $(x-y)(x+y)=41$, so $x=21,y=20$. Since $21$ and $20$ are not powers of $3,2$, there are no solutions for $a,b$, as desired.