Intereting Posts

Nth root of Unity
Proof: if $p$ is prime, and $0<k<p$ then $p$ divides $\binom pk$
Optimal distribution of points over the surface of a sphere
Prove existence of a real root.
Finding Rotation Axis and Angle to Align Two “Oriented Vectors”
Power-reduction formula
Expected number of cards in the stack?
Example about the Reduced cost in the Big-M method?
Formal proof for $\lim_{x\to\infty}x\exp(-x) =0$
How to prove Gauss's Digamma Theorem?
Show that something is a group.
Non-Trivial Induction Order
How far from ZFC is Cohen's second model?
Determining when a certain binomial sum vanishes
What does “rigorous proof” mean?

This is a problem from “Introduction to Mathematics – Algebra and Number Systems” (specifically, exercise set 2 #9), which is one of my math texts. Please note that this isn’t homework, but I would still appreciate hints rather than a complete answer.

The problem reads as follows:

If 3p

^{2}= q^{2}, where $p,q \in \mathbb{Z}$, show that 3 is a common divisor of p and q.

- Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$
- Representability as a Sum of Three Positive Squares or Non-negative Triangular Numbers
- Number Theory Prime Reciprocals never an integer
- A game with two dice
- A slightly stranger Hensel's Lemma
- Prove that two consecutive square free numbers can have arbitrarily large gaps

I am able to show that 3 divides q, simply by rearranging for p^{2} and showing that

$$p^2 \in \mathbb{Z} \Rightarrow q^2/3 \in \mathbb{Z} \Rightarrow 3|q$$

However, I’m not sure how to show that 3 divides p.

**Edit:**

Moron left a comment below in which I was prompted to apply the solution to this question as a proof of $\sqrt{3}$’s irrationality. Here’s what I came up with…

~~[incorrect solution…]~~

…is this correct?

**Edit:**

The correct solution is provided in the comments below by Bill Dubuque.

- Number of representable as sum of 2 squares
- System of equations - modular arithmetic
- Count ways to take pots
- The diophantine equation $x^2+y^2=3z^2$
- Given the first N integers, how many large prime factors can I disallow and still have half the set remaining?
- Convergence or divergence of $\sum\limits_n(-1)^{\pi(n)}\frac1n$ where $\pi(n)$ is the number of primes less than or equal to $n$
- Solving the equation $x^{2}-7^{y}=2$
- Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square
- Rabin-Miller compositeness
- Squares in $(\operatorname{rad}(1)^2+1)\cdot(\operatorname{rad}(2)^2+1)\ldots(\operatorname{rad}(n)^2+1)$

Write $q$ as $3r$ and see what happens.

Below is a **conceptual** proof of the irrationality of square-roots. It shows that this result follows immediately from **unique fractionization** — the uniqueness of the denominator of any reduced fraction — i.e. the least denominator divides every denominator. This in turn follows from the key fact that the set of all possible denominators of a fraction is closed under subtraction so comprises an **ideal** of $\,\mathbb Z,\,$ necessarily principal, since $\,\mathbb Z\,$ is a $\rm PID$. But we can eliminate this highbrow language to obtain the following conceptual high-school level proof:

**Theorem** $\ $ Let $\;\rm n\in\mathbb N.\;$ Then $\;\rm r = \sqrt{n}\;$ is integral if rational.

**Proof** $\ $ Consider the set $\rm D$ of all possible denominators $\,\rm d\,$ for $\,\rm r, \,$ i.e. $\,\rm D = \{ d\in\mathbb Z \,:\: dr \in \mathbb Z\}$. Notice $\,\rm D\,$ is closed under subtraction: $\rm\, d,e \in D\, \Rightarrow\, dr,\,er\in\mathbb Z \,\Rightarrow\, (d-e)\,r = dr – er \in\mathbb Z.\,$

Further $\,\rm d\in D \,\Rightarrow\, dr\in D\ $ by $\rm\ (dr)r = dn\in\mathbb Z, \,$ by $\,\rm r^2 = n\in\mathbb Z.\,$ Thus by the Lemma below,

with $\,\rm d =$ least positive element in $\rm D,\,$ we infer that $\ \rm d\mid dr, \ $ i.e. $\rm\ r = (dr)/d \in\mathbb Z.\ \ $ **QED**

**Lemma** $\ $ Suppose $\,\rm D\subset\mathbb Z \,$ is closed under subtraction and that $\rm D$ contains a nonzero element.

Then $\rm D \:$ has a positive element and the least positive element of $\,\rm D\,$ divides every element of $\,\rm D$.

**Proof** $\rm\,\ \ 0 \ne d\in D \,\Rightarrow\, d-d = 0\in D\,\Rightarrow\, 0-d = -d\in D.\, $ Hence $\rm D$ contains a positive element. Let $\,\rm d\,$ be the least positive element in $\,\rm D.\,$ Since $\rm\: d\,|\,n \!\iff\! d\,|\,{-}n,\,$ if $\rm\ c\in D\,$ is not divisible by $\,\rm d\,$ then we

may assume that $\,\rm c\,$ is positive, and the least such element. But $\rm\, c-d\,$ is a positive element of $\,\rm D\,$ not divisible by $\,\rm d\,$

and smaller than $\,\rm c,\,$ contra leastness of $\,\rm c.\,$ So $\,\rm d\,$ divides every element of $\,\rm D.\ $ **QED**

The proof of the theorem exploits the fact that the denominator ideal $\,\rm D\,$ has the special property that it is closed under multiplication by $\rm\, r.\: $ The fundamental role that this property plays becomes clearer when one learns about Dedekind’s notion of a **conductor ideal**. Employing such yields a trivial one-line proof of the generalization that a Dedekind domain is integrally closed since conductor ideals are invertible so cancellable. This viewpoint serves to generalize and unify all of the ad-hoc proofs of this class of results – esp. those proofs that proceed essentially by descent on denominators. This conductor-based **structural** viewpoint is not as well known as it should be – e.g. even some famous number theorists have overlooked this. See my post here for further details.

Moron’s answer certainly covers your question, but as someone who’s not your instructor I’d like to see a few more details in your ‘proof’ of the first half – can you be more specific about how $q^2/3 \in \mathbb{Z} \Rightarrow 3|q$? While that’s easy, it’s not necessarily trivial, and you’ve elided some details there…

Think about how many times each prime factor must appear on each side of the equation, if you were to break p and q into their prime factorizations. The left side has a 3 in it, how many must the right side have, at least?

Here we go. $3p^2=q^2$ implies that $3$ divides $q$, since $3$ is prime and if a prime divides a product, it divides one of the factors. But then, if $3$ divides $q$, then we also have that $3^2$ divides $q^2$. Hence, by factoring out the 9 on the rhs, we can cancle the 3 on the left hand side and still be left with a three. i.e $3\alpha=p^2$. But then, $3$ divides p, as required.

Try to write out the factorization of the right and left handed sides.

Now compare the order of the 3 on the left and right side, one of them is equal, forcing the other side to become odd. Contradiction.

- Is this a valid partial fraction decomposition?
- Is the “$\mapsto$” notation considered “proper” mathematics?
- How to show there are no simple groups of order 760 using Sylow's theorem
- What is a composition of two binary relations geometrically?
- Exponential of matrices and bounded operators
- Is the proof of $\lim_{\theta\to 0} \frac{\sin \theta}{\theta}=1$ in some high school textbooks circular?
- “This property is local on” : properties of morphisms of $S$-schemes
- Why does Arccos(Sin(x)) look like this??
- Peano axioms with only sets and mapping
- Multichoosing (Stars and bars)
- Continuous function that attain local extrema every point
- A question about Hölder spaces.
- Product of logarithms, prove this identity.
- Predicate logic: How do you self-check the logical structure of your own arguments?
- More than one blocks of infinitely repeating digits in a number