2
$\begingroup$

Show that there are two distinct positive integers such that: $1394|2^a-2^b$

I'm sure pigeon hole principle applies here,but don't recognize holes.Another problem statement is: show that there are two positive integers $a,b$ such that: $$2^a\equiv 2^b\pmod {1394}$$
Of course we have $1394$ cases for division mod $1394$,but what are the pigeons?

$\endgroup$
3
$\begingroup$

Hint:

Consider $2^i \pmod{1394}$ for $1 \leq i \leq \color{blue}{1395}$

$\endgroup$
  • $\begingroup$ So this problem has been VERY simple!!! I was afraid of that!! $\endgroup$ – Hamid Reza Ebrahimi Dec 10 '17 at 5:30
1
$\begingroup$

Note $1394=2 \times 17 \times 41$.

Since $\varphi(17 \times 41) = 16\times 40 = 640$,

then $2^{640} \equiv 1 \pmod{697}$.

Hence $2^{641} \equiv 2 \pmod{1394}$.

In other words, $1394 \mid 2^{641}-2^1$.

Note. Actually, we can do better. Checking the divisors of $640$, we find that $2^{40} \equiv 1 \pmod{697}$. So $1394 \mid 2^{41}-2^1$.

$\endgroup$
  • $\begingroup$ One question, what did you do in that last step when you say "checking the divisors of 640"? $\endgroup$ – Francisco José Letterio Dec 10 '17 at 17:25
  • $\begingroup$ Since $2^{240} \equiv 1 \pmod {697}$, then $H = \{2^1,2^2,2^3,\dots,2^{240}\}$ is a cyclic subgroup of $\mathbb U_{697}$, a multiplicative group with $240$ elements in it. Hence the order of $2$ in $H$ is a divisor of $240$. $\endgroup$ – steven gregory Dec 10 '17 at 19:33

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.