Claim 1 (Well known) : For each prime number $p$ and each natural number $d$ such that $d|p-1$ , there exist exactly $\varphi(d)$ numbers $1 \le x \le p-1$ such that $ord_{p} x = d$. Claim 2 : For each natural number $1 \le x \le p(p-1)$ that $gcd(x , p)=1$ , $ord_{p} x = d$ and $gcd(x , p-1)=d'$ there exist exactly $d'\frac{p-1}{d}$ values for $1 \le y \le p(p-1)$ such that : $$x^y \equiv y^x \equiv 1 \pmod p$$Proof : Since $x^y \equiv 1 \pmod p$ , we have $d=ord_{p} x | y$ and there exist $\frac{p-1}{d}$ proper values $d , 2d , ... , \frac{p-1}{d}d$ for $y$ modulo $p-1$ and also while $y^x \equiv 1 \pmod p$ , if for a primitive root $g$ modulo $p$ we have $g^a \equiv y \pmod p$ ; then we must have $p-1|ay$ and $\frac{p-1}{d'}|a$ which has $d'$ proper distinct values for $a$ modulo $p-1$ and for $y$ modulo $p$. So while $p$ and $p-1$ are coprime , by CRT there exist $d'\frac{p-1}{d}$ proper values for $y$ modulo $p(p-1)$ and our claim is proved. Now one can see that : $$N=\sum_{1 \le x \le p(p-1) , gcd(x , p)=1} {d'_{x}\frac{p-1}{d_{x}}}$$ Claim 3 : $$N=(p-1)^2 (\sum_{d|p-1}{\frac{\varphi(d)}{d}})^2$$Proof : For each number $d|p-1$ , consider all numbers $1 \le x \le p(p-1)$ such that $gcd(x , p-1)=\frac{p-1}{d}$ and suppose that $i_1 , i_2 , ... , i_{\varphi(d)} < d$ are all numbers coprime to $d$ modulo $d$ ; so all numbers $1 \le x \le p(p-1)$ that $gcd(x , p-1)=\frac{p-1}{d}$ are in the form $\frac{p-1}{d}j$ that values of $j$ are such below : $$i_1 , i_2 , ... , i_{\varphi(d)}$$$$i_1+d , i_2+d , ... , i_{\varphi(d)}+d$$$$.$$$$.$$$$.$$$$i_1+(p-1)d , i_2+(p-1)d , ... , i_{\varphi(d)}+(p-1)d$$So since $d|p-1$ and $gcd(d , p)=1$ , for each $1 \le k \le \varphi(d)$ values $i_k , i_k+d , ... , i_k+(p-1)d$ produce a complete residue system modulo $p$ , which by claim $1$ for each $d'|p-1$ , has exactly $\varphi(d')$ values $x$ with $ord_{p} x = d'$ and $\varphi(d')\varphi(d)$ values in total. Thus by Claim 2 we can get : $$N=\sum_{1 \le x \le p(p-1) , gcd(x , p)=1} {\frac{(p-1)^2}{d_{x}d'_{x}}}=(p-1)^2 (\sum_{d|p-1}{\frac{\varphi(d)}{d}})^2$$Which proves our claim. Claim 4 : For natural numbers $m , n \in \mathbb{N}$ that $n|m$ , we have : $$ \frac{\varphi(m)}{m} \le \frac{\varphi(n)}{n}$$Proof :Suppose that $n=p_1^{a_1}...p_k^{a_k}$ and $m=p_1^{b_1}...p_k^{b_k}q_1^{c_1}...q_s^{c_s}$ ; so we can get : $$\frac{\varphi(m)}{m}=\frac{(p_1-1)...(p_k-1)}{p_1...p_k} \frac{(q_1-1)...(q_s-1)}{q_1...q_s}=\frac{\varphi(n)}{n}\frac{(q_1-1)...(q_s-1)}{q_1...q_s} \le \frac{\varphi(n)}{n}$$Which proves our claim. Now by claim $3 , 4$ and since $\varphi(d) \le d$ ; we can get that : $$N=(p-1)^2 (\sum_{d|p-1}{\frac{\varphi(d)}{d}})^2 \le ((p-1)d(p-1))^2$$$$(p-1)^2 (\sum_{d|p-1}{\frac{\varphi(d)}{d}})^2 \ge (p-1)^2(d(p-1) \frac{\varphi(p-1)}{p-1})^2=(\varphi(p-1)d(p-1))^2$$And we're done.