4.II.8B

Numbers and Sets
Part IA, 2002

Suppose that a,ba, b are coprime positive integers. Write down an integer d>0d>0 such that ad1a^{d} \equiv 1 modulo bb. The least such dd is the order of aa modulo bb. Show that if the order of aa modulo bb is yy, and ax1a^{x} \equiv 1 modulo bb, then yy divides xx.

Let n2n \geqslant 2 and Fn=22n+1F_{n}=2^{2^{n}}+1. Suppose that pp is a prime factor of FnF_{n}. Find the order of 2 modulo pp, and show that p1p \equiv 1 modulo 2n+12^{n+1}.