, 2015

(1) Since $\{a_n\}$ is ascending, $a_{n+1} - a_n$ takes a positive integral value for every $n$. So, let $s$ be the minimum value for $a_{n+1} - a_n$ where $n \ge 1$. Then, $s$ is a positive integer.
Let $m$ be one positive integer for which $a_{m+1} - a_m = s$, and let $k$ be an integer satisfying $2^k > p$. Using the fact $a_{2n} = 2a_n$ repeatedly, we get
$$\begin{aligned} a_{2^k(m+1)} - a_{2^k m} &= 2(a_{2^{k-1}(m+1)} - a_{2^{k-1} m}) = \dots \\ &= 2^{k-1}(a_{2(m+1)} - a_{2m}) = 2^k(a_{m+1} - a_m) = 2^k s. \end{aligned}$$

On the other hand, since $a_{n+1}-a_n$ takes values greater than or equal to $s$ for every $n$ satisfying $2^k m \le n \le 2^k (m+1)-1$, we see that $a_{n+1}-a_n = s$ must hold for all such $n$. This means that the sequence $a_{2^k m}, a_{2^k m+1}, \dots, a_{2^k (m+1)}$ forms an arithmetic progression with increment $s$. Suppose that for some pair of integers $i, j$ ($0 \le i < j \le p-1$), $a_{2^k m+i} \equiv a_{2^k m+j} \pmod p$ holds. Then, we see that $a_{2^k m+i} - a_{2^k m+j} = (j-i)s$ must be a multiple of $p$. But this contradicts the fact $p$ is a prime, since both $0 < j-i < p$ and $0 < s \le a_2 - a_1 = a_1 < p$ hold. Thus, we conclude that the remainders obtained by dividing each of $p$ numbers $a_{2^k m}, a_{2^k m+1}, \dots, a_{2^k m+p-1}$ by $p$ are all distinct. In particular, there exists a multiple of $p$ among these numbers, and this proves that $\{a_n\}$ satisfies the requirement for part (1) of the problem.

(2) For a positive integer $n$, let $k_n$ be a non-negative integer for which $2^{k_n} \le n < 2^{k_{n+1}}$ holds. Then, we see that $k_n \le k_{n+1}$ and $k_{2n} = k_n + 1$ are satisfied. Therefore, if we let $a_n = np + 2^{k_n}$, then it is easy to check that the sequence $\{a_n\}$ is ascending. Furthermore, since $p$ is an odd prime, $2^{k_n}$ is not a multiple of $p$, and therefore, neither is $a_n$. Thus the sequence $\{a_n\}$ satisfies the requirement for part (2) of the problem.