Intereting Posts

What does order topology over Ordinal numbers look like, and how does it work?
How do I find out the symmetry of a function?
proving $ e^{\pi} > \pi ^{e}$
Solve the equation $(2^m-1) = (2^n-1)k^2$
Prove that $\left (\frac{1}{a}+1 \right)\left (\frac{1}{b}+1 \right)\left (\frac{1}{c}+1 \right) \geq 64.$
Topology of matrices
If every cyclic subgroup of $G$ is normal so is every subgroup?
Computing diagonal Length of a Square
$\inf_{x\in}f(x)=\inf_{x\in\cap\mathbb{Q}}f(x)$ for a continuous function $f:\to\mathbb{R}$
Example of a linear operator on some vector space with more than one right inverse.
Why is the infinite sphere contractible?
The automorphism group of the real line with standard topology
Prove by mathematical induction that $n^3 – n$ is divisible by $3$ for all natural number $n$
Apparently cannot be solved using logarithms
What are logarithms?

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.

- After swapping the positions of the hour and the minute hand, when will a clock still give a valid time?
- Ambiguity in the Natural Numbers
- Do we really know the reliability of PrimeQ (for $n>10^{16}$)?
- Calculating $a^n\pmod m$ in the general case
- Claim: $a$ has $90 \% $ primes less than $n$ If $n!= 2^s \times a \times b $ and $\lfloor{\frac{a}{b}}\rfloor = 2^{s-2}$
- $t^3$ is never equal to

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.

- How many groups of 4 primes exist such that their sum is a prime and that $p^2+qs$ and $p^2+qr$ are squares?
- Is it possible to find an infinite set of points in the plane where the distance between any pair is rational?
- Permutation Partition Counting
- If $\gcd(a,b)=d$, then $\gcd(ac,bc)=cd$?
- Primality of number 1
- Prove that we always have $ 2n \mid \varphi(m^n+p^n) $
- Self-avoiding walk on $\mathbb{Z}$
- Profinite and p-adic interpolation of Fibonacci numbers
- Find an infinite set of positive integers such that the sum of any two distinct elements has an even number of distinct prime factors
- Tensor product of a number field $K$ and the $p$-adic integers

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.

- What's special about the greatest common divisor of a + b and a – b?
- To find area of the curves that are extension of ellipse
- Proving the AM-GM inequality for 2 numbers $\sqrt{xy}\le\frac{x+y}2$
- On inequalities for norms of matrices
- What is the value of $\sum_{p\le x} 1/p^2$?
- Find the condition on $a$ and $b$ so that the two tangents drawn to the parabola $y^2=4ax$ from a point are normals to the parabola $x^2=4by$
- Different standards for writing down logical quantifiers in a formal way
- Prove that the nuclear norm is convex
- Why isn't an infinite direct product of copies of $\Bbb Z$ a free module?
- Polynomial $p(x) = 0$ for all $x$ implies coefficients of polynomial are zero
- Question about Subrings and integraly closed
- Measurable Cauchy Function is Continuous
- How do you derive the continuous analog of the discrete sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, …$?
- Prove that matrix can be square of matrix with real entries
- Determining whether ${p^{n-2} \choose k}$ is divisible by $p^{n-k -2}$ for $1 \le k < n$