[Bài toán] Cấp của một số nguyên

Bài toán (Korea Final Round 2007)

 Tìm các số nguyên tố $p,q$ thỏa mãn $pq\mid p^p+q^q+1$.

Lời giải :

Bổ đề : Cho các số nguyên tố $p,q,r$ trong đó $p$ lẻ và thỏa mãn $p\mid q^r+1$ thì khi đó $2r\mid p-1$ hoặc $p\mid q^2-1$.

Bài toán :

Từ đề bài ta có $p^p+1\equiv 0(modq)$ và $q^q+1\equiv 0(modp)$

Xét $p=2$ ta có $4+1\equiv 0(modq)\Rightarrow q=5$, thử lại cặp $(2,5)$ thỏa mãn. Tương tự cặp $(5,2)$ cũng thỏa mãn.

Xét các số nguyên tố $p,q$ đều lẻ.

Vì $q\mid p^p+1$ nên áp dụng bổ đề ta có $2p\mid q-1$ hoặc $q\mid p^2-1$.

Nếu $2p\mid q-1\Rightarrow q\equiv 1(modp)\Rightarrow 0\equiv q^q+1\equiv 2(modp)\Rightarrow p=2$ (loại)

Nếu $q\mid p^2-1$ thì $q\mid p-1$ hoặc $q\mid p+1$. Lập luận như trên ta chỉ ra rằng $q\mid p-1$ là vô lí nên phải có $q\mid p+1$. Tuy nhiên thì $p+1$ chẵn và $gcd(q,2)=1$ nên ta có $2q\mid p+1\Rightarrow p+1\ge 2q$.

Hoàn toàn tương tự ta có $q+1\ge 2p$. Suy ra $p+q+2\ge 2(p+q)\Rightarrow p+q\le 2$ và điều này thì vô lí

Kết luận : $\boxed{(p,q)=(2,5),(5,2)}$