Divisibility of $\frac{2^k-a_n}{3^n}$ for all primes. The problem is proving whether $2^k-a_n = 0 \pmod u$, $2^k-a_n = 0\pmod {3^n}$ for a sequence $a_n$ defined $a_{n+1}= 2a_n +3^n$ and $a_1 = 1$, can be solved for any $u$ (Such that u is the biggest number possible so $2^k-a_n = 0 \pmod u$) . I thought that it would be best to start with a prime $u$, but I haven't found any better approaches than just trial and error. This only solved the problem for specific cases but not generally.
This is my first question, so please give feedback on the quality of the question and how I can improve it. Thanks!
Edit: I checked my answer for the base case $a_1 = 1$ and have found that sometimes random prime factors divide $ 2^k -1$ and after looking at the pattern of these factors, I predict that any factors for a prime k will be of the form $2^V *k -1$ if $2^k -1$ itself t isn’t already prime. The problem is finding what values of u in general this covers, and u is the product of all those prime factors so it is hard to generalize.
Edit2: changed u to be the biggest possible number in that case. This is what I originally meant but forgot to add to the problem.
Edit 3: edit 1(for $2^2k +1$ (2k temporarily replacing k) does give U= Gcd((2k+1),$(2^k-1)$) but I don’t know how to prove edit 1 completely.(this is for a prime 2k + 1)
Clarification 1: to make this clearer, I’m trying to find weather we can get any intiger number u we want that divides $2^k-a_n$ The new answer below helps construct any u =$ 3^{something}$ but can it take other values??From my work above, it seems that for any number of the form $2^k -1$ where a prime 2k+1 divides it, it is possible though a proof of this would be hard. (Would need to prove that any factors of $2^k -1$ you can’t just get from eulers generalization of fermats little theorem, would be given by 2k +1 (or maybe $2^{an odd number}$ *k + 1)
Clarification 2: you can choose your k and n to see what values you can get out of u instead of oroving values for all n (which is crazy and I never knew was possible to prove) (I asked for “all primes” in the title, because if we can isolate primes in this way then using edits seen above we probably can for all other intigers too)
 A: In fact, we make the following claim:
THM 1: Let $n$ be any positive integer and let $a$ be any integer satisfying $(3,a)=1$ i.e., $a$ does not have to be prime. Then there is an integer $k$ such that $3^n|(2^k-a)$.
Note that THM 1 establishes all you need; $a$ does not have to be prime; instead $a$ has to just be any integer satisfying $(a,3)=1$. [Note that for $3^n$ [with $n \ge 1$] to divide $(2^k-a)$ that $a$ cannot be a multiple of $3$ so this covers everything.] To establish THM 1, use induction on $n$ to show the following.
Lemma 2: The integer $2$ is primitive in $(\mathbb{Z}/3^n\mathbb{Z})^*$, i.e., every element $a \in (\mathbb{Z}/3^n\mathbb{Z})^*$ can be written $a \equiv_{3^n} 2^k$ for some positive integer $k$. Eqivalently, $2$ generates the entire group $(\mathbb{Z}/3^n\mathbb{Z})^*$.
SKETCH OF PROOF OF Lemma 2: Note that $|(\mathbb{Z}/3^n\mathbb{Z})^*| =2\times 3^{n-1}$, so the smallest positive integer $k$ satisfying $2^k \equiv_{3^n} 1$ must satisfy $k=2 \times 3^{m}$; $m$ a nonnegative integer satisfying $m<n$. So we now use induction as claimed; assume that $n \ge 4$ and that the following is true:
$$2^{2 \times 3^{n-2}} \not \equiv_{3^n} 1.$$ [This can be checked directly for $n=2,3,4$.]
Then to establish Lemma 2, it suffices to show that the following is also true:
$$2^{2 \times 3^{n-1}} \not \equiv_{3^{n+1}} 1.$$ [Make sure you see why this is.] However,
$$2^{2 \times 3^{n-2}} \not \equiv_{3^n} 1$$
$$\implies {\text{ there is an integer $c$}}$$ $${\text{satisfying $(c,3)=1$ s.t. }}$$ $$2^{2 \times 3^{n-2}} = 1 + \Big(c \times 3^{n-1}\Big)$$
$$\implies 2^{2 \times 3^{n-1}} = \Big(2^{2 \times 3^{n-2}}\Big)^3$$ $$= \Big(1 + \Big(c \times 3^{n-1}\Big)\Big)^3$$ $$=1 + 3\Big(c \times 3^{n-1}\Big) + \Big(C×3^{2n-2}\Big)$$ $$\text{for some integer $C$}$$
$$\implies 2^{2 \times 3^{n-1}} \not \equiv_{3^{n+1}} 1,$$
which is what we wanted. $\surd$
Then THM 1 follows immediately from Lemma 2.
ETA: The conclusion of THM 1 hinges on $2$ generating the entire group $(\mathbb{Z}/3^n\mathbb{Z})^*$. There are primes $q$ [namely, $q=7$ and $q=17$ are such primes] for which
$2$ does not generate the entire group $(\mathbb{Z}/q^n\mathbb{Z})^*$. So let $q$ be such a prime and let $a \in$ $(\mathbb{Z}/q^n\mathbb{Z})^*$ such that $a$ is not generated by $2$. Then there is no integer $k$ such that $q^n$ divides $2^k-a$.
If, to elaborate, we were to replace $3$ by $17$ [or any other odd prime $q$ for which $2$ is a square in $(\mathbb{Z}/q\mathbb{Z})^*$], and take $a$ any nonsquare in $(\mathbb{Z}/q\mathbb{Z})^*$, then there is no integer $k$ such that $q$ divides $2^k-a$, nevermind $q^n$ dividing $2^k-a$ for any other positive integer $n$. For example, there is no integer $k$ such that $17$ divides $2^k-12$. Indeed, $2$ is a square in $(\mathbb{Z}/17\mathbb{Z})^*$, and so $2^k$  is a square in $(\mathbb{Z}/17\mathbb{Z})^*$ for all integers $k$, whereas $12$ is not a square in $(\mathbb{Z}/17\mathbb{Z})^*$. So even for $n=1$, there is no integer $k$ such that $2^k \equiv_{17} 12$, nevermind higher powers of $17$.
Similarly, there is no integer $k$ such that $7$ divides $2^k-5$, nevermind $7^n$ dividing $2^k-5$ for general positive integers $n$.
