Find all pairs $(a, p)$ of positive integers, where $p$ is a prime, such that for any pair of positive integers $m$ and $n$ the remainder obtained when $a^{2^n}$ is divided by $p^n$ is non-zero and equals the remainder obtained when $a^{2^m}$ is divided by $p^m$.
1. **Understanding the Problem:**
   We need to find all pairs \((a, p)\) of positive integers, where \(p\) is a prime, such that for any pair of positive integers \(m\) and \(n\), the remainder obtained when \(a^{2^n}\) is divided by \(p^n\) is non-zero and equals the remainder obtained when \(a^{2^m}\) is divided by \(p^m\).

2. **Rewriting the Condition:**
   The given condition implies that \(p^n \mid a^{2^m - 2^n} - 1\) for all \(m > n\).

3. **Claim 1: No \(p > 2\) works.**
   - **Proof:**
     - Take \(m = 2\) and \(n = 1\). This gives \(p \mid a^2 - 1\).
     - Since \(p\) is odd, we can use the Lifting The Exponent (LTE) lemma:
       \[
       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})
       \]
     - Therefore,
       \[
       v_p(a^2 - 1) + v_p(2^{m-n} - 1) \geq n \quad \text{for all } m > n
       \]
     - Taking \(m = n + 1\) and \(n\) sufficiently large, we get a contradiction because \(v_p(2^{m-n} - 1) = v_p(2 - 1) = 0\) for \(p > 2\). Hence, no \(p > 2\) works. \(\blacksquare\)

4. **Claim 2: \(p = 2\) works if and only if \(a\) is odd.**
   - **Proof:**
     - If \(a\) is even, then \(a^{2^2} \equiv 0 \pmod{2^2}\), which is a contradiction. Hence, \(a\) must be odd.
     - We claim that if \(a\) is odd, then \(a^{2^n} \equiv 1 \pmod{2^n}\) for all \(n\).
     - Using the LTE lemma:
       \[
       v_2(a^{2^n} - 1) = v_2(a - 1) + v_2(a + 1) + v_2(2^n) - 1
       \]
     - Since \(a\) is odd, \(a - 1\) and \(a + 1\) are both even, and:
       \[
       v_2(a - 1) \geq 1, \quad v_2(a + 1) \geq 1, \quad v_2(2^n) = n
       \]
     - Therefore,
       \[
       v_2(a^{2^n} - 1) \geq 1 + 1 + n - 1 = n + 1 > n
       \]
     - This shows that \(a^{2^n} \equiv 1 \pmod{2^n}\) for all \(n\). \(\blacksquare\)

5. **Conclusion:**
   Hence, all solutions are \((a, p) = (2k + 1, 2)\) for some \(k \geq 0\).

The final answer is \( \boxed{ (a, p) = (2k + 1, 2) } \) for some \(k \geq 0\).