questions on Poulet numbers and Fermat pseudoprimes I have found the following problems on Poulet numbers and Fermat Poulet numbers. I guess, I can have good explanation to complete my problems here.
I want to prove or disprove the following:

*

*For any positive integer $k$, there exists infinitely many Poulet numbers of the form $(4^k-1)/3$.


*For a prime $k > 3$, the number $(4^k-1)/3$ is Poulet number.


*For any integer $n > 1$, the following formula generates infinitely many Fermat pseudoprimes to base $n$:
$$(n^{nk+k+n-1}-1)/n^2 -1.$$
High regards,
Dr.MM
 A: Lemma 1: If $k$ is any integer $\ge 2$ and $N = (4^k - 1)/3$, then $2^{2k} = 1 \bmod N$.
Proof: We have $2^{2k} - 1 = 4^k - 1 = 3N$, so $N \mid 2^{2k} - 1$. QED.
Lemma 2: If $k \ge 5$ is prime, then $(4^k - 1)/3 = 1 \bmod 2k$. 
Proof: Since $k$ is prime, we have $4^k = 4 \bmod k$. Hence $4^k - 1 = 3 \bmod k$, and thus $(4^k - 1)/3 = 1 \bmod k$; the division by $3$ is valid since $3 \nmid k$. On the other hand, $(4^k - 1)/3$ is odd and hence $(4^k - 1)/3 = 1 \bmod 2$. Since $k$ is odd, this implies $(4^k - 1)/3 = 1 \bmod 2k$. QED.
Theorem: For any prime $k > 3$, the integer $N = (4^k - 1)/3$ is a Fermat pseudoprime to base 2, i.e. $2^N = 2 \bmod N$.
Proof: We know that $N = 1 \bmod 2k$ by lemma 2, so we can write $N = 1 + 2ak$ for some integer $a$. Hence $2^N - 2 = 2^{1 + 2ak} - 2 = 2( (2^{2k})^a - 1)$. But we know $2^{2k} = 1 \bmod N$ by lemma 1, so $(2^{2k})^a = 1^a = 1 \bmod N$. Thus $2^N - 2 = 0 \bmod N$. QED.
This proves (2), and hence clearly also (1), since there are infinitely many primes! I'll leave you to think about (3) for yourself; you might like to see if the same methods give anything in this case.
