Problem

Source: Iran MO 3rd round 2023 NT exam , P2

Tags: number theory, prime numbers



Let $N$ be the number of ordered pairs $(x,y)$ st $1 \leq x,y \leq p(p-1)$ and : $$x^{y} \equiv y^{x} \equiv 1 \pmod{p}$$where $p$ is a fixed prime number. Show that : $$(\phi {(p-1)}d(p-1))^2 \leq N \leq ((p-1)d(p-1))^2$$where $d(n)$ is the number of divisors of $n$