0
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ How do I determine what such an $N$ is? $\endgroup$ – user72195 Oct 4 '13 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.