MHB Can You Solve These Number Theory Challenges?

[Poirot1]

1)Prove that x,y are positive integers such that $x^2=y^2-9y$, then x=6 or 20.

2) Let p and q be distinct primes. Show that $p^{q-1}+q^{p-1}=1$ (modpq)

Hint for 2) Use Fermats little theorem.

 

[Opalg]

Re: 2 Number theory challenge

1)Prove that x,y are positive integers such that $x^2=y^2-9y$, then x=6 or 20.

Multiply the equation by $4$ to get $4y^2-4x^2-36y=0$, which can be factorised as $(2y+2x-9)(2y-2x-9) = 81$. The only possibilities are $$2y+2x-9 = \left\{\begin{matrix}1\\ 3\\9 \\ 27 \\ 81 \end{matrix}\right.,\qquad 2y-2x-9 = \left\{\begin{matrix}81\\ 27\\ 9\\ 3 \\ 1 \end{matrix}\right.. $$ Subtract the second of these from the first to get $4x = \left\{\begin{matrix}-80\\ -24\\ \phantom{-1}0\\ \phantom{-}24 \\ \phantom{-}80 \end{matrix}\right..$ Reject the first three cases because $x$ is positive, and we are left with $x = 6$ or $20.$

 

[Poirot1]

Better method for 1) relies on the following fact: if a and b are coprime positive integers such that ab is a square, then a and b are both squares.