### Communities

tag:snake search within a tag
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
created:<1w created < 1 week ago
post_type:xxxx type of post
Q&A

# Proving that $p\mid (p+1776)$ if $p$ is a prime and $p(p+1776)$ is a perfect square

+4
−0

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.

Why does this post require moderator attention?
Why should this post be closed?

+4
−0

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.

Why does this post require moderator attention?

+4
−0

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.

Why does this post require moderator attention?