# Is a Fermat's little theorem "recursive" case possible?

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$$.

• 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)?
– Dirk
Apr 24 '17 at 7:58
• @Bemte is strictly an equality, $2^p=$ something, I do not mean $2^p \equiv$ something (this is what I guess from your question). Apr 24 '17 at 8:06

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...

• 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$... Apr 24 '17 at 8:26
• 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$.
– Dirk
Apr 24 '17 at 8:29
• oooh that is totally right, good point. Understood! Working with $\pmod{2^t}$ was neat. Thank you. Apr 24 '17 at 8:34
• 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. Apr 24 '17 at 8:39

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)$

• 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. Apr 24 '17 at 8:45

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.