Bài toán Tìm các số nguyên tố $p,q$ thỏa mãn $p^q+q^p+1$ chia hết cho $pq$ 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$ khi đó thì $2r\mid p-1$ hoặc $p \mid q^2-1$. Chứng minh bổ đề : Từ giả thiết ta có $q^{2r}\equiv 1\;(mod\;p)\Rightarrow ord_p(q)\mid 2r\Rightarrow ord_p(q)\in \left \{ 1,2,r,2r \right \}$ Mà theo định lí $Fermat$ nhỏ thì $q^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(q)\mid p-1$ Nếu $ord_p(q)=1$ thì $q-1\equiv 0\;(mod\;p)\Rightarrow p\mid q^2-1$ Nếu $ord_p(q)=2$ thì $q^2\equiv 1\;(mod\;p)\Rightarrow p\mid q^2-1$ Nếu $ord_p(q)=r$ thì $r\mid p-1$ mà $p-1$ chẵn và $gcd(2,r)=1$ nên $2r\mid p-1$ Nếu $ord_p(q)=2r$ thì $2r \mid p-1$ Tóm lại bổ đề được chứng minh BÀI TOÁN : Từ đề bài ta suy ra $q \mid p^q+1$ và $p \mid q^p+1$. Nếu $p=2$ thì ta có $q\mid 2^{q}+1$ hay $2^{q}\equiv -1\;(mod\;q)$. Theo định lí $Fermat$ nhỏ thì $2^{q}\equiv 2\;(mod\;q)$ Suy ra $-1\equiv 2\;(mod\;q)\Rightarrow q=3$. Tương tự nếu $q=2$ thì $p=3$ Bây giờ, ta xét các số nguyên tố $p,q$ đều lẻ. Khi đó vì $q\mid p^{q}+1$ nên theo bổ đề trên thì ta có $2q \mid q-1$ hoặc $q\mid p^2-1$. Rõ ràng trường hợp $2q \mid q-1$ không xảy ra do đó phải có $q \mid p^2-1$. Suy ra $q\mid (p-1)$ hoặc $q\mid (p+1)$. Nếu như $q\mid p-1\Rightarrow p^{q}+1\equiv 2\;(mod\;q)$, mâu thuẫn. Do vậy $q\mid p+1\Rightarrow 2q \mid p+1$ (vì $p+1$ chẵn và $gcd(2,q)=1$) Suy ra $p+1\geq 2p$. Tương tự $q+1\geq 2p$. Từ đó $p+q+2\geq 2(p+q)\Leftrightarrow p+q\leq 2$ và đây là điều vô lí Kết luận : $\boxed{(p,q)=(2,3),(3,2)}$

Cấp của một số nguyên

Bài toán Tìm các số nguyên tố $p, q$ thỏa mãn $p^{q} + q^{p} + 1$ chia hết cho $pq$

Lời giải :

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

Chứng minh bổ đề :

Từ giả thiết ta có $q^{2 r} \equiv 1 (m o d p) \Rightarrow or d_{p} (q) ∣ 2 r \Rightarrow or d_{p} (q) \in {1, 2, r, 2 r}$

Mà theo định lí $F er ma t$ nhỏ thì $q^{p - 1} \equiv 1 (m o d p) \Rightarrow or d_{p} (q) ∣ p - 1$

Nếu $or d_{p} (q) = 1$ thì $q - 1 \equiv 0 (m o d p) \Rightarrow p ∣ q^{2} - 1$

Nếu $or d_{p} (q) = 2$ thì $q^{2} \equiv 1 (m o d p) \Rightarrow p ∣ q^{2} - 1$

Nếu $or d_{p} (q) = r$ thì $r ∣ p - 1$ mà $p - 1$ chẵn và $g c d (2, r) = 1$ nên $2 r ∣ p - 1$

Nếu $or d_{p} (q) = 2 r$ thì $2 r ∣ p - 1$

Tóm lại bổ đề được chứng minh

BÀI TOÁN :

Từ đề bài ta suy ra $q ∣ p^{q} + 1$ và $p ∣ q^{p} + 1$ .

Nếu $p = 2$ thì ta có $q ∣ 2^{q} + 1$ hay $2^{q} \equiv - 1 (m o d q)$ . Theo định lí $F er ma t$ nhỏ thì $2^{q} \equiv 2 (m o d q)$

Suy ra $- 1 \equiv 2 (m o d q) \Rightarrow q = 3$ .

Tương tự nếu $q = 2$ thì $p = 3$

Bây giờ, ta xét các số nguyên tố $p, q$ đều lẻ.

Khi đó vì $q ∣ p^{q} + 1$ nên theo bổ đề trên thì ta có $2 q ∣ q - 1$ hoặc $q ∣ p^{2} - 1$ .

Rõ ràng trường hợp $2 q ∣ q - 1$ không xảy ra do đó phải có $q ∣ p^{2} - 1$ .

Suy ra $q ∣ (p - 1)$ hoặc $q ∣ (p + 1)$ .

Nếu như $q ∣ p - 1 \Rightarrow p^{q} + 1 \equiv 2 (m o d q)$ , mâu thuẫn.

Do vậy $q ∣ p + 1 \Rightarrow 2 q ∣ p + 1$ (vì $p + 1$ chẵn và $g c d (2, q) = 1$ )

Suy ra $p + 1 \geq 2 p$ . Tương tự $q + 1 \geq 2 p$ .

Từ đó $p + q + 2 \geq 2 (p + q) \Leftrightarrow p + q \leq 2$ và đây là điều vô lí

Kết luận : $(p, q) = (2, 3), (3, 2)$