Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
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?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

2 answers

+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?
You might want to add some details to your flag.

1 comment thread

Thank you for your answer! I see from your proof that the crucial step is the fact that for prime $p$... (1 comment)
+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?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »