Proving that $p\mid (p+1776)$ if $p$ is a prime and $p(p+1776)$ is a perfect square
Problem: Suppose $p$ is a prime number and $p(p+1776)$ is a perfect square. Prove that $p\mid (p+1776)$.
From the assumption of the problem, $p(p+1776)=k^2$ for some positive integer $k$. This does not help much. Intuitively, one can write $p(p+1776)=p^2m^2$ for some integer $m$ due to the fundamental theorem of arithmetic: in order to have a complete square, the factor $p$ should appear twice. One can then easily conclude that $p\mid (p+1776)$ since $p+1776=pm^2$. But I don't find a formal way to show this intuition.
2 answers
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| msh210 | (no comment) | Sep 16, 2022 at 03:22 |
Inspired by Derek Elkins's excellent answer, I have the following proof.
By the assumption, we have $p(p+1776)=k^2$ for some integer $k$ and thus $p\mid k^2$. Then, Euclid's lemma implies that $p\mid k$. It follows that $k=mp$ for some integer $m$ and thus $(mp)^2=k^2=p(p+1776)$, which implies by cancellation that $m^2p=p+1776$. The proof is now complete.
Note: Euclid's lemma is also used in the proof of the fundamental theorem of arithmetic.
0 comment threads
You basically have it.
I'll give an overly detailed rendition of an informal proof below.
As you state, the assumption is that $p(p+1776) = k^2$ for some natural number $k$ with $p$ a prime. We want to show that $p\mid p + 1776$, or, equivalently, $p + 1776 = pm$ for some natural $m$.
Proof: Via the Fundamental Theorem of Arithmetic, $k$ has some unique prime factorization so $k = \prod_i {p_i}^{n_i}$ where all the $p_i$ are prime. $k^2$ is then clearly $\prod_i ({p_i}^{n_i})^2$. Since $p \mid p(p + 1776)$, we have $p \mid k^2$ so there's some $i$ such that $p = p_i$. This is because for a prime $p$, $p \mid rs$ if and only if $p \mid r$ or $p \mid s$, and $p \mid q$ for a prime $q$ if and only if $q = p$. In symbols we have $$p \mid \prod_i {p_i}^{2n_i} \iff \bigvee_i p \mid {p_i}^{2n_i} \iff \bigvee_i p \mid p_i \iff \exists i. p = p_i$$ where $\iff$ is "if and only if" and $\bigvee$ is a variadic disjunction. Choose $j$ such that $p = p_j$.
We thus have $p(p+1776) = k^2 = p^2 m$ where $m = p^{2n_i - 2} \prod_{i \neq j} {p_i}^{2n_i}$, so by cancelling $p$ from both sides we have $p + 1776 = p m$ which is exactly what it means for $p$ to divide $p + 1776$. $\square$
The Fundamental Theorem of Arithmetic is likely overkill for this problem, so it may be interesting to find a proof that doesn't rely on it.
1 comment thread
0 comment threads