# Assume that $\phi_n=2^{2^n}+1$ then g.c.d($\phi_n,\phi_m$) = 1…

Assume that if $\phi_n=2^{2^n}+1$ then g.c.d($\phi_n,\phi_m$) = 1 whenever $n$ is not equal to $m$. Using this assumption, prove that for each $n$ there exist $n$ consecutive integers $N,N + 1,...,N + n - 1$ such that the first is divisible by $\phi_1$; the second by $\phi_2$; the third by $\phi_3;...$and the $n$th by $\phi_n$. When $n=2$ what is the least possible value of $N$? When $n$ = 3?

I have no idea how to go about completing this problem

• Chinese Remainder Theorem. – Daniel Fischer Oct 4 '13 at 22:02
• i still do not know how to go about using that in this case – user72195 Oct 4 '13 at 22:13

You want to find an $N$ such that
$$\phi_k \mid (N-1+k), \quad 1 \leqslant k \leqslant n.$$
That means you want $N \equiv 1 - k \pmod{\phi_k}$ for $1 \leqslant k \leqslant n$. Since the $\phi_k$ are coprime (assumed, but easy to prove), the Chinese remainder theorem guarantees the existence of solutions to the simultaneous congruences, unique modulo $\prod\limits_{k=1}^n \phi_k$.
For $n = 2$, you want to find the smallest positive $N$ such that $\phi_1 = 5 \mid N$, and $\phi_2 = 17 \mid (N+1)$. So $N \equiv 16 \pmod{17}$ and $N \equiv 0 \pmod{5}$. For $n = 3$, you additionally want $N \equiv 255 \pmod{257}$. Note that the smallest solution to that is also a solution to the $n = 2$ case, just not the smallest, so it differs by a multiple of $5\cdot 17$ from the smallest solution for the $n = 2$ case.
• How do I determine what such an $N$ is? – user72195 Oct 4 '13 at 22:37