Let $p|a^{2^x}-c$ then $p^x|p^{x+1}|a^{2^{x+1}}-c=c^2-c$ so if we take $p^x>c$ we get $c=1$ or $c=0$. If $c=0$ we have $p|a^2$ and then $p^n|a^{2^n}$ which is true If $c=1$ then $p|a^2-1$ and: If $p=odd$ we have $U_p(a^{2^x}-1)=U_p((a^2)^{2^{x-1}}-1)=Up(a^2-1)+U_p(2^{x-1})=Up(a^2-1)$ contradiction So $p=2$ which works

Note that the given condition implies that $p^n \mid a^{2^m-2^n}-1$ for all $m>n$. We have the following 2 Claims, which solve the problem. Claim 1: No $p>2$ works. Proof: Take $m=2$ and $n=1$ to obtain that $p \mid a^2-1$. Hence, since $p$ is odd we obtain, by LTE, $v_p(a^{2^m-2^n}-1)=v_p((a^2)^{2^{m-1}-2^{n-1}}-1)=v_p(a^2-1)+v_p(2^{m-1}-2^{n-1})=v_p(a^2-1)+v_p(2^{m-n}-1)$ Therefore, $v_p(a^2-1)+v_p(2^{m-n}-1) \geq n$ for all $m>n$, which is a contradiction by taking $m=n+1$ and $n$ sufficiently large $\blacksquare$ Claim 2: $p=2$ works if and only if $a$ is odd. Proof Note that if $a$ is even, then $a^{2^2} \equiv \pmod 2^2$ is equal to $0$, a contradiction. Hence, $a$ is odd. We claim that, in this case, $a^{2^n} \equiv 1 \pmod 2^n$ for all $n$. Indeed, by LTE, $v_2(a^{2^n}-1)=v_2(a-1)+v_2(a+1)+v_2(2^n)-1 \geq 1+1+n-1=n+1>n,$ as desired $\blacksquare$ Hence, all solutions are $(a,p)=(2k+1,2)$ for some $k \geq 0$.

LTE can be easily avoided, will post when I can.

Answer. $(1,p)$ for any prime $p$ and $(a,2)$ for any odd positive integer $a$ Suppose the common remainder is $1 \leq r \leq p-1$ (it has to be in this range due to $n=1$ and since it is non-zero from the problem condition). For $a^{2} = c_1p + r$ and $a^4 = c_2p^2 + r$ we have \[c_{2}p^{2} + r = a^{4} = (a^{2})^2 = (c_1p + r)^2 = c_1^2p^{2} + 2rc_1p + r^2\]so $r(r-1) = p(c_{2}p - c_1^2p - 2c_1r)$. Hence $p$ divides $r(r-1)$ and since $p$ does not divide $r$ (else $r=0$, contradiction), it must be the case that $p$ divides $r-1$ and from $1 \leq r \leq p-1$ we obtain $r=1$. So we are now looking for the pairs $(a,p)$, such that $p^n$ divides $a^{2^n} - 1$ for all positive integers $n$. We have the factorization \[ a^{2^n} - 1 = (a-1)(a+1)(a^2 + 1)\cdots (a^{2^{n-1}}+1). \] Suppose firstly that $p\geq 3$. Then from $a^{2^n} = c_np^n + 1$ for all $n$ we have $a^{2^n} \equiv 1 \pmod p$ for all $n$, so every factor apart from $a-1$ gives remainder $2$ and is not divisible by $p$. Hence each of these factors is not a multiple of $p$ and so $p^n$ must divide $a-1$ for all $n$, which is possible only for $a=1$. Conversely, for $a=1$ the integer $a^{2^n}-1 = 0$ is divisible by $p^n$ for all $p$ and $n$. Now let $p=2$. A necessary condition for $a^{2^n}- 1$ to be even is $a$ to be odd. Conversely, if $a$ is odd, then all factors (which are $n+1$ in amount) are even, so the whole product is divisible by $2^{n+1}$ (and in particular, by $2^n$). Remark. The divisibility $2^{n+1} \mid a^{2^n} - 1$ also follows from Euler's theorem.

I claim that the answer if $(1,p)$ where $p>2$ is a prime, and that $(a,2)$ where $a$ is an odd integer. The first case clearly works, and for the second case we clearly have that $2\mid a^2-1$ as $a$ is an odd integer. Now I claim that the remainder for this $p=2$ case is always $=1$. Moreover we have that $1$ is also odd, and that $2^n$ is an even integer; so this suffices all the conditions for the LTE lemma for $\nu_{2}$. Thus we have $\nu_{2}(a^{2^n}-1)=\nu_{2}(a^2-1)+\nu_{2}(2^n/2)=\nu_{2}(a^2-1)+n-1\ge n$ which is what we wanted. Let the remainder be $r$. Now initially fix $d$, then we have,\[a^{2^d}\equiv r\pmod{p};\qquad\ a^{2^{d+1}}\equiv r\pmod{p^{d+1}}.\]Now, then we get, \begin{align*} p^d\mid p^{d+1}\mid a^{2^{d+1}}-r&\implies a^{2^{d+1}}\equiv r\pmod{p^d}\\ &\implies \left(a^{2^d}\right)^2\equiv r\\ &\implies r^2\equiv r .\end{align*}Now if $r(r-1)\not=0$, then upon varying $d$, for a sufficiently large $d$, we get a contradiction. So we get that $r(r-1)=0\implies r=1$ as we are given that the remainder is non-zero. So this finally gives us that,\[a^{2^n}\equiv 1\pmod{p^n},\quad\forall\; n\ge 1.\] Now if $p>2$. Set $n=1$ to get $p\mid a^2-1$, which also gives that $\operatorname{gcd}(p,a)=1$. Now for any general $n$, we have that, \begin{align*} &p^n\mid a^{2^n}-1\\ \implies&\nu_{p}(a^{2^n}-1)\ge \nu_{p}(p^n)\\ \implies&\nu_{p}((a^2)^{2^{n-1}}-1)\ge n\\ \implies&\nu_{p}(a^2-1)+\nu_{p}(2^{n-1})\ge n\\ \implies&\nu_{p}(a^2-1)\ge n ,\end{align*}which gives a contradiction unless $a^2-1=0$, which further means $a=1$. Now if $p=2$, then upon setting $n=1$ gives that, $2\mid a^2-1$, which further means that $a$ is odd; and we are done.

Let $n+k=m$ so that $a^{2^n}\equiv r\pmod{p^{n}}$ and $a^{{2^n}^{2^k}}\equiv r^{2^k}\equiv r\pmod{p^{n}}$. For $n=1$, $r\equiv r^2\equiv r^4\cdots\pmod{p} \Longrightarrow r^2-r\equiv r(r-1)\equiv 0\pmod{p}$. By the problem statement, $r\neq0 \Longrightarrow r\equiv1\pmod{p}$. $r<p$ so $r=1$. Now, let $2^{n^{2^k}}=X$ so that $a^X\equiv a^{X+1}\cdots\equiv 1\pmod{p}$. Then $a\equiv 1\pmod{p}$ is forced. If $a=1$, we see that it always works for any $p$. $a^2-1=xp, a^4-1=yp^2 \Longrightarrow xp(xp+2)=yp^2$. If $p\neq2$, this only happens when $x=p \Longrightarrow a^2-1=p^2$ which never works. However, if $p=2$, note that if we have $a^{2^k}-1=2^ks, a^{2^{k+1}}-1=(a^{2^k}-1)(a^{2^k}+1)=2^ks(2l)=2^{k+1}sl, (a^{2^k}+1)=2l$ where $l$ is an integer. WWe want the latter to have one extra factor of $p=2$ or make $(a^{2^k}+1)=2l$ possible, which is always achievable when $a\equiv 1\pmod{2}$. Edit: I forgot to mention that the last part showing $p=2$ works for all $a\equiv 1\pmod{2}$, the induction argument stems from the base case $k=1$ which yields $a^2-1=2s$ which is true given $a\equiv 1\pmod{2}$

$\boxed{ANSWER:(p,a)=(2,2k+1),(p,1)}$ claim 1:$p|a^2-1$ proof:$p(1,p)\implies p|a^2-1$,1 $p(2,p)\implies p|p^2|a^4-1$,2 From 1 and 2 we get $p|a^4-a^2\implies p|a^2-1$ claim 2:if $p>2\implies a=1$ proof:we know that$p^{n}|a^{2^{n}}-1\implies v_p(a^{2^{n}}-1)\geq v_p(p^n)$ $v_p(a^{2^{n}}-1)=v_p((a^2)^{2^{n}}-1)=v_p(a^2-1)+v_p(2^{n-1})=v_p(a^2-1)\geq n$ which is contradiction because of $n$ being very big unless $a^2-1=0\implies a=1$ claim 3:$p=2\implies a=2k+1$ proof:if $p=2\implies 2^n|a^{2^{n}}-1$ Thanks to Euler we know that (if $2\nmid a$) $a^{2^{n-1}}\equiv 1\pmod{2^n}\implies a^{2^{n}}=(a^{2^{n-1}})^2\equiv 1^2=1\pmod{2^n}\implies 2^n|a^{2^{n}}-1.$