0
$\begingroup$

Reading about Fermat's little theorem, I started to think about recursivity. Is a Fermat's little theorem case like the following one possible (initially thought for a prime power of $2$)?

$$2^p = pk_1+2\\k_1=2^{t_1}, t_1\in\Bbb N, p \in \Bbb P$$

Where $k_1$ is again a power of $2$? Another way of writing the expression, is possible the following expression?:

$$2^p=p(2^{t_1})+2\\t_1\in\Bbb N, p \in \Bbb P$$

  1. Writing the expression in a paper, it seems at first sight that there is no clear restriction regarding the existence of an example, but I was not able to find any valid $t$ for some $p$ in the easiest case above mentioned, that just needs to hold for some $t_1 \in \Bbb N$:

$$(k_1=)\frac{2^p-2}{p}=2^{t_1}$$

  1. Indeed, if an example of question $1$ is possible, can be $t_1$ a prime number as well? Can we have a infinitely recursive expression like this?

$$2^p=p(t_1(t_2(t_3(\cdots)+2)+2)+2)+2\\p, t_i \in \Bbb P$$

Probably there is a simple restriction I cannot see right now that makes this impossible. I tried to make a simple code to search for some example, but was unsuccessful. Any insights are very welcomed!

Disclaimer: (added from the comments) just for the sake of completeness: when I wrote the question I was thinking about a more generic version of this, in

$$p_1k_1+p_2=p_2^{p_1},p_1,p_2 \in \Bbb P$$

where then $k_1=p_3^{p_4},p_3,p_4 \in \Bbb P$ and then recursively $k=p_3^{p_4}=p_4k_2+p_3$ etc. But it seemed too complex to think about it, so I reduced the problem to powers of $2$ to grab the idea. Maybe a more generic version is possible because the restrictions might not be so strict as in the case of powers of $2$.

$\endgroup$
2
  • $\begingroup$ Do you want $2^p = p(2^t) + 2$ be an equality in the integers, or do you want it modulo some number (if yes: which one)? $\endgroup$
    – Dirk
    Apr 24 '17 at 7:58
  • $\begingroup$ @Bemte is strictly an equality, $ 2^p= $ something, I do not mean $ 2^p \equiv $ something (this is what I guess from your question). $\endgroup$
    – iadvd
    Apr 24 '17 at 8:06
1
$\begingroup$

So by Fermats little theorem, we know that there exists and integer $r$ such that $2^p = pr + 2$, and you are asking if $r$ can be a power of $2$ again?

For that let's assume that $r = 2^t$. Then $t \leq p$ and we can thus look at the problem mod $r = 2^t$. We will get $$0 \equiv 2^p \equiv p2^t + 2 \equiv 2 \mod{2^t}$$ and for $2^t$ to divide $2$, we get $t = 1$ or $t = 0$.

The case $t = 0$ gives us the following modulo $2$: $$0 \equiv 2^p \equiv p + 2 \equiv p \mod{2}$$ and as $p$ is prime, this only leaves $p = 2$ and thus your equation becomes $4 = 2+2$.

The case $t = 1$ gives us $2^p = 2p+2$ and thus $p = 2^{p-1} - 1$. This is a Mersenne number and it is known and easy to see that such a number is prime only if the exponent of $2$ is prime. For $p-1$ and $p$ to both be prime, we need $p = 3$, thus your initial equation becomes $8 = 3\cdot 2 + 2$.

As all this are only very few cases, I don't see where we can do any recursion here...

$\endgroup$
4
  • $\begingroup$ thanks for the feedback... but I do not understand why you put a $0 \equiv$ at the beginning of your first expression: does it mean $0 \equiv 2^p \pmod{2^t}$? if $2^t \lt 2^p$ then the residue of dividing $2^p$ by $2^t$ cannot be $0$, because $p$ is not a multiple of $t$... $\endgroup$
    – iadvd
    Apr 24 '17 at 8:26
  • $\begingroup$ Yes, that's what I mean and yes, it can as we have powers here. We have $t < p$, so say $p = t+s$ for some positive $s$. Then $2^p = 2^t \cdot 2^s$ is $0$ modulo $2^t$. $\endgroup$
    – Dirk
    Apr 24 '17 at 8:29
  • $\begingroup$ oooh that is totally right, good point. Understood! Working with $\pmod{2^t}$ was neat. Thank you. $\endgroup$
    – iadvd
    Apr 24 '17 at 8:34
  • $\begingroup$ just for completeness: when I wrote the question I was thinking about a more generic version of this, in $p_1k_1+p_2=p_2^{p_1}, p_1,p_2 \in \Bbb P$ where then $k_1=p_3^{p_4}, p_3, p_4 \in \Bbb P$ and then recursively $k=p_3^{p_4}=p_4k_2+p_3$ etc. But it was too difficult to think about it, so I reduced the problem to powers of $2$ to catch the idea. Maybe a more generic version is possible because the restriction is not so strict. $\endgroup$
    – iadvd
    Apr 24 '17 at 8:39
1
$\begingroup$

The only solution is $2^3=3 \cdot 2^1+2$

The restriction is $2^p-2 \equiv 0 \pmod 6$

$2^p-2=2 \cdot(2^{(p-1)}-1)=2 \cdot (2^{\frac{p-1}{2}}+1) \cdot (2^{\frac{p-1}{2}}-1)$

$\endgroup$
1
  • $\begingroup$ thank you for the feedback +1 for the good idea of splitting the power so one of the parts must be a multiple of $3$! that was really neat. $\endgroup$
    – iadvd
    Apr 24 '17 at 8:45
1
$\begingroup$

In $$2^t = p\cdot 2^k +2 \implies \left \{ \begin{matrix} k=1, t \gt 1 \\ k>1,t=1 \end{matrix} \right. $$ because two numbers with high powers of $2$ as factors cannot have a difference of $2$, instead their difference must have $2^{\min(t,k)}$ as factor.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.