Problem Solving in NT (Day 1 of Week 1)

[Romania TST 7 2009, Problem 3] Show that there are infinitely many pairs of prime numbers $(p,q)$ such that $p\mid 2^{q-1}-1$ and $q\mid 2^{p-1}-1$.

Proof: We begin with the lemma, 

Lemma: Let $p\mid 2^{2^n}+1$ then $p\equiv 1\pmod  2^{n+2}$

Proof: Note that ord$_p(2)=2^{n+1}$ $$\implies 2^{n+1}|p\implies p\equiv 1\pmod 2^{n+1}\implies p\equiv 1\pmod 8$$

$$\implies 2^{\frac{p-1}{2}}\equiv 1\pmod p\implies 2^{n+1}\mid \frac{p-1}{2}$$

So consider any prime $p$ dividing $2^{2^{n}}+1$ and $q$ to be prime factor of $2^{2^{n+1}}+1$.

Then we get that $p\equiv 1 \pmod 2^{n+2}$ and we get that $q\equiv 1\pmod 2^{n+3}$.

Note that $$p\mid 2^{n+1}-1\mid 2^{n+3}-1 \mid 2^{q-1}-1$$

Moreover, $$q\mid 2^{n+2}-1\mid 2^{p-1}-1$$

So for any $n$ we get $p,q$!

[China TST 2005] $n$ is a positive integer, $F_n=2^{2^{n}}+1$. Prove that for $n \geq 3$, there exists a prime factor of $F_n$ which is larger than $2^{n+2}(n+1)$.

Proof: Consider the prime factorization, $$2^{2^n}+1= {p_1}^{a_1}\dots {p_k}^{a_k}.$$ Assume $p_1$ is the smallest.

Note that $p_i\equiv 1\pmod 2^{n+2}$. Moreover FTSOC, $p_i=1+2^{n+2}b_i, b_i\le n$

Then taking $\mod 2^{(n+2)\times 2}=2^{2n+4}$. We get $${p_i}^{a_i}\equiv {1+2^{n+2}b_i}^{a_i}\equiv 1+a_i2^{n+2}b_i\pmod 2^{2n+4}$$

Now, we take $F_n\pmod  2^{2n+4}$ in both ways. 

Note that $$F_n\equiv 1 \pmod  2^{2n+4}\implies 1+2^{n+2}\sum (a_ib_i)\equiv 1 \pmod  2^{2n+4}\implies \sum a_ib_i\equiv 0\pmod 2^{n+2}$$

So $$\sum a_i\ge 2^{n+2}/n$$

So $$F_n=2^{2^{n}}+1=\prod (1+2^{n+2}q_i)^{a_i} \ge  (1+2^{n+2}q_1)^{\sum a_i} $$

$$\ge (1+2^{n+2}q_1)^{2^{n+2}/n}\ge (1+2^{n+2})^{2^{n+2}/n}\ge (2^{n+2})^{2^{n+2}/n}\ge 2^{2^{n+2}}$$

But $2^{2^{n+2}}\ge 2^{2^n}+1$