Basic Math Challenge - August 2018

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #1
12,890
9,523

Main Question or Discussion Point

Summer is coming and brings a new basic math challenge! Enjoy! For more advanced problems you can check our other intermediate level math challenge thread!

RULES:

1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored. Solutions will be posted around 15th of the following month.
2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.
5) Mentors, advisors and homework helpers are kindly requested not to post solutions, not even in spoiler tags, for the challenge problems, until 16th of each month. This gives the opportunity to other people including but not limited to students to feel more comfortable in dealing with / solving the challenge problems. In case of an inadvertent posting of a solution the post will be deleted.

QUESTIONS:

1. Given a non-negative, monotone decreasing sequence ##(a_n)_{n \in \mathbb{N}}\subseteq \mathbb{R}\,.## Prove that ##\sum_{n \in \mathbb{N}}a_n## converges if and only if ##\sum_{n \in \mathbb{N}_0}2^na_{2^n}## converges.

2. (solved by @lpetrich ) Calculate
$$
\sum_{k=0}^\infty \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m!}\cdot \left(\dfrac{(2k)!}{k!}\right)^2 \dfrac{2^{-6k-2}}{(2k-m+1)!}
$$
3. (solved by @nuuskur , @lpetrich ) Show that the product ##P=xyz## of a Pythagorean triple ##x^2+y^2=z^2## is always divisible by ##60\,|\,P##. Since this is an easy problem, please make sure you won't forget to name an argument!

4. (solved by @lpetrich, resp. resolved ) Given two vector fields ##v,w\, : \,\mathbb{R}^2 \longrightarrow \mathbb{R}^2## by
$$
v(x,y)=\begin{bmatrix}
y \\ x-y
\end{bmatrix}\; , \;w(x,y)=\begin{bmatrix}
y-x \\ -y
\end{bmatrix}
$$
and two curves in ##\mathbb{R}^2## given as:
##\gamma_1## is the half circle from ##(0,-1)## to ##(0,1)## with radius ##1## and origin ##(0,0)##, run anti-clockwise from bottom to top.
##\gamma_2## is the straight line segments from (-1,0) correction: ##(0,-1)## to ##(1,0)## and from ##(1,0)## to ##(0,1)##, also run through from bottom to top.
  • Compute all ##4## path integrals of ##v## and ##w## with both paths ##\gamma_1,\gamma_2\,.##
  • Determine whether ##v## or ##w## have potentials.
5. (solved by @nuuskur ) Show that ##\mathbb{Z}[x]/\langle x^2+2x+4\; , \;5 \rangle \cong \mathbb{Z}_5[4+\sqrt{2}]## are isomorphic rings.

6. (solved by @lpetrich ) Calculate
$$
\int_0^{\pi} \dfrac{\sin(\varphi)}{3\cos^2(\varphi)+2\cos(\varphi)+3}\,d\varphi
$$
7. (solved by @lpetrich ) Integrate $$\int_1^5 \dfrac{dx}{\sqrt{x^2+3x-4}}$$
8. (solved by @Math_QED ) The random waiting time ##X## on a telephone hotline is characterized by the distribution function ##F## with
$$
F(x) =
\begin{cases}
0 & \text{if } x < 0 \\
a-be^{-\lambda x}1 & \text{if } x \geq 0
\end{cases}
$$
for some parameters ##a, b, \lambda \in \mathbb{R}## with ##\lambda > 0\,.## We further assume that ##P(X=0)=0.5##, i.e. there is a ##50\,\%## chance not to wait at all, and ##P(X>1[min])=0.25##.
  • Determine the parameters with the given information, such that ##F## is actually a distribution function.
  • Can the distribution be described by a density function? Why? If yes, calculate the density function.
9. (solved by @Danny Sleator ) A princess decided one day to go swimming in the circular lake far from the castle of her father. As soon as she got into the water, suddenly a witch appeared, who wanted to kidnap the girl. The princess swam quickly into the middle of the lake to think of an escape plan. She noticed three things:
  • The witch can run four times as fast as I can swim.
  • The witch always tries to stay closest to me.
  • On land, I'm faster than the witch.
Is there a way for the princess to escape, how? Why doesn't she have a chance to escape?

10. (solved by @Dewgale ) Let ##f\, : \,\mathbb{R}^2 \longrightarrow \mathbb{R}## be defined as ##f(x,y)=x(x-1)^2-2y^2\,.## Determine all critical points of ##f##, decide whether there are extrema, and which, and at last consider, whether ##f## has global extrema or not.
 
Last edited:

Answers and Replies

  • #2
984
173
Solution for Question 4:
The path interval of vector ##V = \{V_x, V_y\}## over ##X = \{x,y\}## with parameter ##t## is:
$$ I = \int V \cdot dX = \int V \cdot \frac{dX}{dt} dt $$
The vectors are ##u = \{y, x-y\}## and ##v = \{y-x,-y\}##.
The curves of integration are
$$ \gamma_1 = \{\sin t, - \cos t\} \text{ for } t \in [0,\pi] \\
\gamma_2 = \{t,0\} \text{ for } t \in [-1,1] \text{ and } \{1-t,t\} \text{ for } t \in [0,1] $$
The integrals are:
  • ##(u,\gamma_1)##: ##0##
  • ##(u,\gamma_2)##: ##- \frac12##
  • ##(v,\gamma_1)##: ##- \frac{\pi}{2}##
  • ##(v,\gamma_2)##: ##- \frac12##
How much intermediate manipulation should I show?

If a vector field ##V## has potential ##P##, then ##V = \nabla P = \{\frac{\partial P}{\partial x}, \frac{\partial P}{\partial y} \}##. It is easy to show that this results in the field's curl (asymmetrized gradient) vanishing, or in two dimensions, ##\frac{\partial V_x}{\partial y} = \frac{\partial V_y}{\partial x}##. I'm not sure about the converse, that vanishing curl implies a potential. The path integral of ##V## is
$$ \int V \cdot dX = \int \nabla P \cdot dX = P $$
For ##u##, we get ##1 = 1##, and for ##v##, we get ##1 = 0##, So ##v## does not have a potential. For ##u##, the potential is, from integration of each component,
$$P = xy + F(y) = xy - \frac12 y^2 + G(x) = xy - \frac12 y^2 + P_0 $$
 
Last edited:
  • #3
984
173
Solution for Question 6:
Let
$$ I = \int_0^{\pi} \dfrac{\sin(\varphi)}{3\cos^2(\varphi)+2\cos(\varphi)+3}\,d\varphi $$
Change variables from ##\varphi## to ##x = \cos\varphi##. The bounds of integration become ##x = 1## and ##x = -1## and the differential ##dx = - \sin\varphi \, d\varphi##. With this change of variables, the integral becomes
$$ I = \int_{-1}^1 \dfrac {dx}{3x^2 + 2x + 3} $$
Complete the square in the integrand's denominator:
$$ I = \frac13 \int_{-1}^1 \dfrac {dx}{(x + 1/3)^2 + (8/9)} $$
Change variables again, to ##x = -1/3 + (2\sqrt{2}/3) \tan y ## with limits of integration ##y = - \arctan(1/\sqrt{2})## and ##y = \arctan(\sqrt{2})##.
$$ I = \frac{1}{2\sqrt{2}} \int_{-\arctan(1/\sqrt{2})}^{\arctan(\sqrt{2})} dy $$
giving
$$ I = \frac{1}{2\sqrt{2}} (\arctan(1/\sqrt{2}) + \arctan(\sqrt{2})) = \frac{\pi}{4\sqrt{2}} $$
 
Last edited:
  • #4
984
173
Solution for Question 7:
Start with
$$ I = \int_1^5 \dfrac{dx}{\sqrt{x^2+3x-4}} $$
The argument of the square root is ##(x^2 + 3x - 4) = (x-1)(x+4) = (x+(3/2))^2 - (5/2)^2##. This suggests a change of variables: ##x = -(3/2) + (5/2)\cosh y## with limits of integration ##y = \text{arccosh} \,1 = 0## and ##y = \text{arccosh} (13/5)##. The argument of the square root becomes ##(5/2)^2 \sinh^2 y##, the differential becomes ##(5/2) \sinh y ##, and we find
$$ I = \int_0^{\text{arccosh}(13/5)} dy = \text{arccosh} \frac{13}{5} = \log
\left(\frac{13}{5} + \frac{12}{5}\right) = \log 5 $$
using ##\text{arccosh} \, x = \log(x + \sqrt{x^2-1})##.
 
Last edited:
  • #5
12,890
9,523
Solution for Question 4:
The path interval of vector ##V = \{V_x, V_y\}## over ##X = \{x,y\}## with parameter ##t## is:
$$ I = \int V \cdot dX = \int V \cdot \frac{dX}{dt} dt $$
The vectors are ##u = \{y, x-y\}## and ##v = \{y-x,-y\}##.
The curves of integration are
$$ \gamma_1 = \{\sin t, - \cos t\} \text{ for } t \in [0,\pi] \\
\gamma_2 = \{t,0\} \text{ for } t \in [-1,1] \text{ and } \{1-t,t\} \text{ for } t \in [0,1] $$
The integrals are:
  • ##(u,\gamma_1)##: ##0##
  • ##(u,\gamma_2)##: ##- \frac12##
  • ##(v,\gamma_1)##: ##- \frac{\pi}{2}##
  • ##(v,\gamma_2)##: ##- \frac12##
How much intermediate manipulation should I show?

If a vector field ##V## has potential ##P##, then ##V = \nabla P = \{\frac{\partial P}{\partial x}, \frac{\partial P}{\partial y} \}##. It is easy to show that this results in the field's curl (asymmetrized gradient) vanishing, or in two dimensions, ##\frac{\partial V_x}{\partial y} = \frac{\partial V_y}{\partial x}##. I'm not sure about the converse, that vanishing curl implies a potential. The path integral of ##V## is
$$ \int V \cdot dX = \int \nabla P \cdot dX = P $$
For ##u##, we get ##1 = 1##, and for ##v##, we get ##1 = 0##, So ##v## does not have a potential. For ##u##, the potential is, from integration of each component,
$$P = xy + F(y) = xy - \frac12 y^2 + G(x) = xy - \frac12 y^2 + P_0 $$
Your results are correct. It's my fault that I had this typo. The two paths had been meant to start and end at the same points. However, since you haven't worked out the integrals, which I find you should have done for at least one of them for demonstration, we can turn this in an advantage and leave the corrected version for someone else who wants to do it.

The curl argument is correct, too. In the corrected version with two paths for the same connection, there is also an argument by the use of these paths.

So do me a favor and don't add your calculations, so that somebody else can still find the alternative reasoning and give us some explicit calculations.
 
  • #6
12,890
9,523
Solution for Question 6:
Let
$$ I = \int_0^{\pi} \dfrac{\sin(\varphi)}{3\cos^2(\varphi)+2\cos(\varphi)+3}\,d\varphi $$
Change variables from ##\varphi## to ##x = \cos\varphi##. The bounds of integration become ##x = 1## and ##x = -1## and the differential ##dx = - \sin\varphi \, d\varphi##. With this change of variables, the integral becomes
$$ I = \int_{-1}^1 \dfrac {dx}{3x^2 + 2x + 3} $$
Complete the square in the integrand's denominator:
$$ I = \frac13 \int_{-1}^1 \dfrac {dx}{(x + 1/3)^2 + (8/9)} $$
Change variables again, to ##x = -1/3 + (2\sqrt{2}/3) \tan y ## with limits of integration ##y = - \arctan(1/\sqrt{2})## and ##y = \arctan(\sqrt{2})##.
$$ I = \frac{1}{2\sqrt{2}} \int_{-\arctan(1/\sqrt{2})}^{\arctan(\sqrt{2})} dy $$
giving
$$ I = \frac{1}{2\sqrt{2}} (\arctan(1/\sqrt{2}) + \arctan(\sqrt{2})) = \frac{\pi}{4\sqrt{2}} $$
Correct.

Another way to solve this integral is the Weierstraß or tangent half angle substitution.
Here we set ##t := \tan\left(\frac{1}{2}\varphi \right) ##and get
$$
\sin(\varphi)=\dfrac{2t}{1+t^2}\, , \,\cos(\varphi)=\dfrac{1-t^2}{1+t^2}\, , \,d\varphi = \dfrac{2}{1+t^2}\,dt
$$
which is often a nice way to turn trig functions into polynomials.
 
  • #7
12,890
9,523
Solution for Question 7:
Start with
$$ I = \int_1^5 \dfrac{dx}{\sqrt{x^2+3x-4}} $$
The argument of the square root is ##(x^2 + 3x - 4) = (x-1)(x+4) = (x+(3/2))^2 - (5/2)^2##. This suggests a change of variables: ##x = -(3/2) + (5/2)\cosh y## with limits of integration ##y = \text{arccosh} \,1 = 0## and ##y = \text{arccosh} (13/5)##. The argument of the square root becomes ##(5/2)^2 \sinh^2 y##, the differential becomes ##(5/2) \sinh y ##, and we find
$$ I = \int_0^{\text{arccosh}(13/5)} dy = \text{arccosh} \frac{13}{5} = \log
\left(\frac{13}{5} + \frac{12}{5}\right) = \log 5 $$
using ##\text{arccosh} \, x = \log(x + \sqrt{x^2-1})##.
Also correct.

Here's another way: In this case we can make use of the Euler Substitution ##\sqrt{x^2+3x-4}=(x+4)t##.

In order to solve this integral, we look at the zeros in the denominator which are ##x=-4## and ##x=1\,.## We choose the former and proceed by an Euler substitution: ##\sqrt{x^2+3x-4}=\sqrt{(x+4)(x-1)}=(x+4)t\,.## We then have
$$x=\dfrac{1+4t^2}{1-t^2}\; , \;\sqrt{x^2+3x-4}=\dfrac{5t}{1-t^2}\; , \;dx = \dfrac{10t}{(1-t^2)^2}\,dt$$
 
  • #8
984
173
Solution for Question 2: (mistake discovered in one of the sums. Solution removed until it can be corrected)
 
  • #9
12,890
9,523
Solution for Question 2: (mistake discovered in one of the sums. Solution removed until it can be corrected)
Thanks.
 
  • #10
984
173
My would-be solution for Question 2. I'm posting it here for reference in case the original question statement had had a typo in a certain place.
We start with
$$ S = \sum_{k=0}^\infty \sum_{m=0}^k \dfrac{\sqrt{5}^m}{m!}\cdot \left(\dfrac{(2k)!}{k!}\right)^2 \dfrac{2^{-6k-2}}{(2k-m+1)!} $$
The second sum is over 0 to k, and I don't know if that was intended or not. If it was a typo for (2k+1), then my would-be solution will work. Here is that would-be solution:

The sums are a sum over k of a sum over m, so I rearrange ##S## so that the k-only terms are outside the m terms:
$$ S = \sum_{k=0}^\infty \dfrac{(2k)! (2k)!}{2^{6k+2} k! k!} \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m! \cdot (2k-m+1)!} $$
The sum over m is rather obviously a binomial-theorem expansion:
$$ \dfrac{(1+\sqrt{5})^{2k+1}}{(2k+1)!} = \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m! \cdot (2k-m+1)!} $$
This gives us
$$ S = \sum_{k=0}^\infty \dfrac{(2k)! (2k)!}{2^{6k+2} (2k+1)! k! k!} (1+\sqrt{5})^{2k+1} =
\sum_{k=0}^\infty \dfrac{(2k)!}{2^{6k+2} (2k+1) k! k!} (1+\sqrt{5})^{2k+1} $$
This can be found with a generalization of the binomial theorem:
$$ (1+x)^a = 1 + a x + \dfrac{a(a-1}{2!} x^2 + \dfrac{a(a-1)(a-2)}{3!} x^3 + \cdots = \sum_{k=0}^{\infty} \dfrac{\Gamma(a+k)}{\Gamma(a) k!} x^k $$
using the Euler gamma function. Take a = -1/2 and reverse the sign of x:
$$ \dfrac{1}{\sqrt{1-x}} = 1 + (1/2) x + \dfrac{1/2 \cdot 3/2}{2!} x^2 + \dfrac {1/2 \cdot 3/2 \cdot 5/2}{3!} x^3 + \cdots = \sum_{k=0}^{\infty} \dfrac{(2k)!}{2^{2k} k! k!} x^k $$
Taking the square of x and integrating gives us
$$ \int \dfrac{dx}{\sqrt{1-x^2}} = \arcsin x = \sum_{k=0}^{\infty} \dfrac{(2k)!}{2^{2k} (2k+1) k! k!} x^{2k+1} $$
To get ##S##, we set ##x = (1 + \sqrt{5})/4##, giving ##x^{2k+1} = (1 + \sqrt{5})^{2k+1}/2^{4k+2}##, and
$$ S = \arcsin \dfrac{1 + \sqrt{5}}{4} = \frac{\pi}{2} - \arccos\dfrac{1 + \sqrt{5}}{4} = \frac{\pi}{2} - \frac{\pi}{5} = \frac{3}{10} \pi $$

I will prove that ##\cos (\pi/5) = (1 + \sqrt{5})/4##. From trigonometric addition identities, it is easy to show that ##\cos (5x) = 16 \cos^5 x - 20 \cos^3 x + 5 \cos x##. For ##x = \pi/5## and ##\cos (\pi/5) = w##, we find ##-1 = 16w^5 - 20w^3 + 5w##. Adding 1 to both sides and factoring gives us ##(w+1) ( 4w^2 - 2w - 1)^2 = 0##. The first factor gives a trivial solution, while the second factor gives us ##w = (1 \pm \sqrt{5})/4##. One can then find which solution corresponds to ##\cos (\pi/5)## by numerical evaluation. Though not exact, the error bars for this numerical evaluation can easily be made much less than the difference between the solutions. Like with IEEE 754 floating-point numbers, the standard for most hardware floating-point numbers.
 
  • Like
Likes dRic2
  • #11
12,890
9,523
My would-be solution for Question 2. I'm posting it here for reference in case the original question statement had had a typo in a certain place.
We start with
$$ S = \sum_{k=0}^\infty \sum_{m=0}^k \dfrac{\sqrt{5}^m}{m!}\cdot \left(\dfrac{(2k)!}{k!}\right)^2 \dfrac{2^{-6k-2}}{(2k-m+1)!} $$
The second sum is over 0 to k, and I don't know if that was intended or not. If it was a typo for (2k+1), then my would-be solution will work. Here is that would-be solution:

The sums are a sum over k of a sum over m, so I rearrange ##S## so that the k-only terms are outside the m terms:
$$ S = \sum_{k=0}^\infty \dfrac{(2k)! (2k)!}{2^{6k+2} k! k!} \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m! \cdot (2k-m+1)!} $$
The sum over m is rather obviously a binomial-theorem expansion:
$$ \dfrac{(1+\sqrt{5})^{2k+1}}{(2k+1)!} = \sum_{m=0}^{2k+1} \dfrac{\sqrt{5}^m}{m! \cdot (2k-m+1)!} $$
This gives us
$$ S = \sum_{k=0}^\infty \dfrac{(2k)! (2k)!}{2^{6k+2} (2k+1)! k! k!} (1+\sqrt{5})^{2k+1} =
\sum_{k=0}^\infty \dfrac{(2k)!}{2^{6k+2} (2k+1) k! k!} (1+\sqrt{5})^{2k+1} $$
This can be found with a generalization of the binomial theorem:
$$ (1+x)^a = 1 + a x + \dfrac{a(a-1}{2!} x^2 + \dfrac{a(a-1)(a-2)}{3!} x^3 + \cdots = \sum_{k=0}^{\infty} \dfrac{\Gamma(a+k)}{\Gamma(a) k!} x^k $$
using the Euler gamma function. Take a = -1/2 and reverse the sign of x:
$$ \dfrac{1}{\sqrt{1-x}} = 1 + (1/2) x + \dfrac{1/2 \cdot 3/2}{2!} x^2 + \dfrac {1/2 \cdot 3/2 \cdot 5/2}{3!} x^3 + \cdots = \sum_{k=0}^{\infty} \dfrac{(2k)!}{2^{2k} k! k!} x^k $$
Taking the square of x and integrating gives us
$$ \int \dfrac{dx}{\sqrt{1-x^2}} = \arcsin x = \sum_{k=0}^{\infty} \dfrac{(2k)!}{2^{2k} (2k+1) k! k!} x^{2k+1} $$
To get ##S##, we set ##x = (1 + \sqrt{5})/4##, giving ##x^{2k+1} = (1 + \sqrt{5})^{2k+1}/2^{4k+2}##, and
$$ S = \arcsin \dfrac{1 + \sqrt{5}}{4} = \frac{\pi}{2} - \arccos\dfrac{1 + \sqrt{5}}{4} = \frac{\pi}{2} - \frac{\pi}{5} = \frac{3}{10} \pi $$

I will prove that ##\cos (\pi/5) = (1 + \sqrt{5})/4##. From trigonometric addition identities, it is easy to show that ##\cos (5x) = 16 \cos^5 x - 20 \cos^3 x + 5 \cos x##. For ##x = \pi/5## and ##\cos (\pi/5) = w##, we find ##-1 = 16w^5 - 20w^3 + 5w##. Adding 1 to both sides and factoring gives us ##(w+1) ( 4w^2 - 2w - 1)^2 = 0##. The first factor gives a trivial solution, while the second factor gives us ##w = (1 \pm \sqrt{5})/4##. One can then find which solution corresponds to ##\cos (\pi/5)## by numerical evaluation. Though not exact, the error bars for this numerical evaluation can easily be made much less than the difference between the solutions. Like with IEEE 754 floating-point numbers, the standard for most hardware floating-point numbers.
Yes, you are right, the upper summation index had been wrong and although you copied the error, your solution is the one of the corrected version. This special problem has been shifted from month to month that I couldn't find the original anymore. I think it was either a copy error of mine or a sloppy Wikipedia entry. Nevertheless, the result is correct and I appreciate your effort for ##\operatorname{arccos}\left( \dfrac{1+\sqrt{5}}{4} \right)= \dfrac{\pi}{5}##. Btw., nice work to show the series expansions of ##\operatorname{arcsin}##, ##\operatorname{arccos}##, resp.
 
  • #12
984
173
Solution for Question 3:
Consider Pythagorean triples {x, y, z}, positive integers satisfying ##x^2 + y^2 = z^2##. Is their product P = ##x y z## divisible by 60?

From Pythagorean triple - Wikipedia, every Pythagorean triple is given by
$$ x = k \cdot (m^2 - n^2) ,\ y = k \cdot (2mn) ,\ z = k \cdot (m^2 + n^2) $$
where k is a positive integer, and m and n are two coprime integers with one of them even, one of them odd. The article also contains a proof of that theorem.

From this formula, ##P = k^3 (2mn (m^4 - n^4))##. Since the divisibility must be true for all ##k##, it must be true for ##k = 1##, so I use that restriction: ##P = 2mn (m^4 - n^4)##.

Since one of m and n must be even, this means that P must be divisible by 2*2 = 4.

For higher primes p, I set the even one of m and n to ##2(pa+s)## and the odd one to ##(pb+t)## where a and b are nonnegative integers and s and t are nonnegative integers that range between 0 and p-1. I then checked on whether P is divisible by p for each value of s and t. That is the case for 3 and 5, but not for any of the other primes that I tested. The highest one I tested was the 100th one, 541, and Mathematica got bogged down there.

So I find that P is always divisible by a number that is at least 4*3*5 = 60. I will now look for an upper limit for the always-divisible number. For that, I use the smallest Pythagorean triple, {3,4,5}. Its product is 60. So 60 is the largest number that divides every Pythagorean-triple product.
 
  • #13
12,890
9,523
Solution for Question 3:

Consider Pythagorean triples {x, y, z}, positive integers satisfying ##x^2 + y^2 = z^2##. Is their product P = ##x y z## divisible by 60?

From Pythagorean triple - Wikipedia, every Pythagorean triple is given by
$$ x = k \cdot (m^2 - n^2) ,\ y = k \cdot (2mn) ,\ z = k \cdot (m^2 + n^2) $$
where k is a positive integer, and m and n are two coprime integers with one of them even, one of them odd. The article also contains a proof of that theorem.

From this formula, ##P = k^3 (2mn (m^4 - n^4))##. Since the divisibility must be true for all ##k##, it must be true for ##k = 1##, so I use that restriction: ##P = 2mn (m^4 - n^4)##.

Since one of m and n must be even, this means that P must be divisible by 2*2 = 4.
Why can you (still) assume this? In the original Wiki version a factor ##2## could have been shifted into ##k##, but as you set ##k=1## you need a different argument.
For higher primes p, I set the even one of m and n to ##2(pa+s)## and the odd one to ##(pb+t)## ...
Ehm, what?
Did you mean: "Let ##m=2(pa+s)## be even and ##n=pb+t## odd."?
... where a and b are nonnegative integers and s and t are nonnegative integers that range between 0 and p-1. I then checked on whether P is divisible by p for each value of s and t.
Where?
That is the case for 3 and 5, but not for any of the other primes that I tested. The highest one I tested was the 100th one, 541, and Mathematica got bogged down there.

So I find that P is always divisible by a number that is at least 4*3*5 = 60. I will now look for an upper limit for the always-divisible number. For that, I use the smallest Pythagorean triple, {3,4,5}. Its product is 60. So 60 is the largest number that divides every Pythagorean-triple product.
The proof as it stands has flaws, and as I mentioned, that this is an easy question, even without the Wikipedia theorem, all used properties should be explicitly mentioned. You don't need to test any primes, only ##2^2,3,5## are stated.
 
Last edited:
  • #14
984
173
I will try Question 3 again.
Statement of the problem. A Pythagorean triplet is a triplet of positive integers ##(x,y,z)## that satisfies the Pythagorean equation ##x^2 + y^2 = z^2##. Consider the product of the members of a Pythagorean triplet ##P = x y z##. What is their greatest common denominator D?

Upper limit. An upper limit on D comes from the smallest possible value of P. The smallest Pythagorean triplet is (3,4,5), and its P value = 60. Thus, D must evenly divide 60.

Divisor-product theorem. This theorem greatly simplifies the proof, since it is much easier to find some relatively-prime divisors of D than D itself. In particular, we need only check 4, 3, and 5, because they are relatively prime, and because their product is the upper limit on D found earlier.

The theorem: for positive integers a, b, x, and for a and b being relatively prime, if ##a | x## and ##b | x## then ##ab | x## (the | means "evenly divides"). Proof: The first divisibility, ##a | x##, implies ##x = ay## for some positive-integer y. The second divisibility involves dividing by b, and since a is not divisible by b, y must be: ##y = bz## for some positive-integer z. Thus, ##x = a(bz) = (ab)z## thus proving the theorem.

In the next parts, I use modular arithmetic, and that is justified by ##a | x## being equivalent to ##x \mod a = 0##. I use modular arithmetic because of its greater compactness of notation: 1 mod 2 instead of (2n+1).

Divisor 4. I start out with the prime factor, and I do modulo 2. The triplet members are either 0 or 1, and the squares of them are likewise either 0 or 1. There are only four possible combinations that satisfy the Pythagorean equation:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 mod 2

Thus, a Pythagorean triplet contains either three even numbers or one even number and two odd numbers. For all even numbers, one can divide out 2: ##x = 2x', y = 2y', z = 2z'##. This process can be repeated until at least one triplet member is odd. Thus, (all even) = (2 to some power) * (one even, two odd). That means that we only have to do the case of one even, two odd, since its results will also hold for the all-even case.

Looking for further constraints, I multiply the modulus by 2, and do modulo 4. The even one is either 0 or 2, and the odd ones either 1 or 3. The even one's square is always 0, and the odd ones' squares are always 1. The only possible combinations are:

0 + 1 = 1, 1 + 0 = 1 mod 4

The remaining one would give 1 + 1 = 0 mod 4. That means that of (x,y,z), z is always odd and x and y are one even, one odd.

Looking even further, I multiply the modulus by 2 again, and do modulo 8. The even one is 0, 2, 4, or 6, and its squares are 0 or 4. The odd ones are 1, 3, 5, 7, and 9, and their squares are all 1. The only possible combinations are:

0 + 1 = 1, 1 + 0 = 1 mod 8

The remaining ones would give 4 + 1 = 1, 1 + 4 = 1 mod 8. The even one is thus 0 or 4 mod 8, meaning that the even one is always divisible by 4. So one of x and y is divisible by 4 and the other one is odd. Also, z is odd.

This means that product P is always divisible by 4.

Divisor 3. I do modulo 3 here. The triplet members are 0, 1, or 2, and their squares are 0, 1, or 1. The only possible combinations are:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 mod 3

So (1) all three of x, y, and z are divisible by 3, or (2) one of x and y is divisible by 3 and the other one is not. Also, z is not divisible by 3.

This means that product P is always divisible by 3.

Divisor 5. I do modulo 5 here. The triplet members are 0, 1, 2, 3, or 4, and their squares are 0, 1, 4, 4, or 1. The only possible combinations are:

0 + 0 = 0, 1 + 4 = 0, 4 + 1 = 0, 1 + 0 = 1, 0 + 1 = 1, 4 + 0 = 4, 0 + 4 = 4 mod 5

Thus, either one of x, y, and z, or else all three of them, are divisible by 5.

This means that product P is always divisible by 5.

Combined Divisor. Using the divisor-product theoream gives ##4 \cdot 3 \cdot 5 = 60##, the maximum value found earlier for D, the GCD of the P's. Thus, D = 60, the result that we wanted to prove.
 
Last edited:
  • #15
12,890
9,523
I will try Question 3 again.

Statement of the problem
. A Pythagorean triplet is a triplet of positive integers ##(x,y,z)## that satisfies the Pythagorean equation ##x^2 + y^2 = z^2##. Consider the product of the members of a Pythagorean triplet ##P = x y z##. What is their greatest common denominator D?

Upper limit. An upper limit on D comes from the smallest possible value of P. The smallest Pythagorean triplet is (3,4,5), and its P value = 60. Thus, D must evenly divide 60.

Divisor-product theorem. This theorem greatly simplifies the proof, since it is much easier to find some relatively-prime divisors of D than D itself. In particular, we need only check 4, 3, and 5, because they are relatively prime, and because their product is the upper limit on D found earlier.

The theorem: for positive integers a, b, x, and for a and b being relatively prime, if ##a | x## and ##b | x## then ##ab | x## (the | means "evenly divides"). Proof: The first divisibility, ##a | x##, implies ##x = ay## for some positive-integer y. The second divisibility involves dividing by b, and since a is not divisible by b, y must be:
This is true but not as obvious as you suggest. You used a property which prime numbers have, but you only have coprime numbers. Since we're all used to integers, this indeed appears obvious. However, in general, i.e. for other rings, this cannot be concluded in this way. E.g. it looks as if you implicitly used the unique factorization theorem, which in arbitrary rings isn't available. Maybe you had another proof in mind, but as you didn't write it, I cannot know.
##y = bz## for some positive-integer z. Thus, ##x = a(bz) = (ab)z## thus proving the theorem.

In the next parts, I use modular arithmetic, and that is justified by ##a | x## being equivalent to ##x \mod a = 0##. I use modular arithmetic because of its greater compactness of notation: 1 mod 2 instead of (2n+1).

Divisor 4. I start out with the prime factor, and I do modulo 2. The triplet members are either 0 or 1, and the squares of them are likewise either 0 or 1. There are only four possible combinations that satisfy the Pythagorean equation:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 mod 2

Thus, a Pythagorean triplet contains either three even numbers or one even number and two odd numbers. For all even numbers, one can divide out 2: ##x = 2x', y = 2y', z = 2z'##. This process can be repeated until at least one triplet member is odd. Thus, (all even) = (2 to some power) * (one even, two odd). That means that we only have to do the case of one even, two odd, since its results will also hold for the all-even case.

Looking for further constraints, I multiply the modulus by 2, and do modulo 4. The even one is either 0 or 2, and the odd ones either 1 or 3.
Why? ##3## is odd and ##2\cdot 3 = 6 = 2 \,\operatorname{mod}4\,.## If you had squared it first, then ##(2n+1)^2=1\,\operatorname{mod}4## but you haven't. Squaring first does the job, because odd numbers squared have a remainder one modulo four, which also excludes the case ##1+1=0 \,(2)## since even numbers squared are divisible by four and ##1+1\neq 0\,(4)\,.##
The even one's square is always 0,...
I can't follow you anymore. If you multiply by ##2##, which you did, your equation becomes ##2x^2+2y^2=2z^2## which isn't Pythagorean anymore. So how can you still reason with squares? The same argument applies to the next step. Maybe I don't see what you meant, but that's the price you pay if you put a distance between your arguments and your equation by modulo.
... and the odd ones' squares are always 1. The only possible combinations are:

0 + 1 = 1, 1 + 0 = 1 mod 4

The remaining one would give 1 + 1 = 0 mod 4. That means that of (x,y,z), z is always odd and x and y are one even, one odd.
From here on I have difficulties to follow you. Up to now you have (with the corrections above) w.l.o.g. ##x=2u\; , \;y=2v+1\; , \;z=2w+1## and ##y^2=z^2=1\,\operatorname{mod}(2),(4)##.
Looking even further, I multiply the modulus by 2 again, and do modulo 8.
Now what exactly do you multiply by two? The remainders so far, then you have no squares anymore. The entire equation ##x^2+y^2=z^2##, then you have no squares anymore. The single numbers ##x,y,z##, then you made them divisible by four.
The even one is 0, 2, 4, or 6, and its squares are 0 or 4. The odd ones are 1, 3, 5, 7, and 9, and their squares are all 1. The only possible combinations are:

0 + 1 = 1, 1 + 0 = 1 mod 8

The remaining ones would give 4 + 1 = 1, 1 + 4 = 1 mod 8. The even one is thus 0 or 4 mod 8, meaning that the even one is always divisible by 4. So one of x and y is divisible by 4 and the other one is odd. Also, z is odd.

This means that product P is always divisible by 4.

Divisor 3. I do modulo 3 here. The triplet members are 0, 1, or 2, and their squares are 0, 1, or 1. The only possible combinations are:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 mod 3

So (1) all three of x, y, and z are divisible by 3, or (2) one of x and y is divisible by 3 and the other one is not. Also, z is not divisible by 3.

This means that product P is always divisible by 3.

Divisor 5. I do modulo 5 here. The triplet members are 0, 1, 2, 3, or 4, and their squares are 0, 1, 4, 4, or 1. The only possible combinations are:

0 + 0 = 0, 1 + 4 = 0, 4 + 1 = 0, 1 + 0 = 1, 0 + 1 = 1, 4 + 0 = 4, 0 + 4 = 4 mod 5

Thus, either one of x, y, and z, or else all three of them, are divisible by 5.

This means that product P is always divisible by 5.

Combined Divisor. Using the divisor-product theoream gives ##4 \cdot 3 \cdot 5 = 60##, the maximum value found earlier for D, the GCD of the P's. Thus, D = 60, the result that we wanted to prove.
The cases ##3## and ##5## are correct. The case ##4## is sloppy at least, or I don't see it. This is by the way the only case, the representation ##x=u^2-v^2\, , \,y=u^2+v^2\, , \,z=2uv## does a good job, since only ##2\,|\,uv(u-v)(u+v)(u^2+v^2)## will be left to show.

Maybe, I'm too stupid to follow your arguments, but ##0+1=1## is simply to few information to actually see anything.
 
  • #16
527
351
I'll try question 3, looks like something that can be given the ol' modular arithmetic treatment.
Let positive integers ##x,y,z ## satisfy ##x^2+y^2 = z^2 ##. We will show ##60\mid xyz ##.
To this end it suffices to show ##k\mid xyz ## where ##k=3,4,5 ##. It then stands that the least common multiple (which is ##60##) divides the product.

The following is implied by (a.k.a addition in ##Z_n ##)
[tex]
x\equiv a\pmod{n}\ \&\ y\equiv b\pmod{n} \implies x+y\equiv a+b\pmod{n}.
[/tex]

1. It holds that ##x## or ##y## is a multiple of ##3##. Indeed, we have
[tex]
(3k+1)^2 = 9k^2 + 6k + 1 = 3(3k^2+2k)+1\quad\mbox{and}\quad (3k+2)^2 = 9k^2 + 12k +4 = 3(3k^2 + 4k +1) +1
[/tex]
Assuming neither is a multiple of ##3## would mean ##z^2\equiv 2\pmod{3} ## which contradicts the above.

2. At least one factor is divisible by ##4##. We can parametrise
[tex]
x = p^2-q^2\quad y = 2pq\quad z = p^2+q^2,
[/tex]
with ##(p,q)=1##. If ##p## or ##q## is even, we're done. Suppose they are both odd. The square of an odd number is of the form ##4m+1## yielding ##p^2-q^2 \equiv 0\pmod{4} ##.


3. At least one factor is divisible by ##5##. Possible squares modulo ##5## are ##0,1,4##. If none of the factors is a multiple of ##5## then the possibilities for ##x^2+y^2-z^2\pmod{5} ## include (up to commutativity)
[tex]
1+1-1 =1\quad 1+1-4 = 3\quad 1+4-1 = 4\quad 1+4-4 =1\quad 4+4-1 = 2\quad 4+4-4 = 4\quad
[/tex]
none of which is ##0##, contradicting the initial equality.
 
Last edited:
  • #17
527
351
For question ##5## I don't understand the construction. I'd recognise something like ##R[x] / \langle m(x) \rangle ## where the quotient is taken w.r.t the ideal generated by ##m##. But what is ##Z[x] / \langle m(x), n \rangle ##? What is the meaning of the parameter ##n##? What sort of ideal is that?

Ah it's a constant polynomial!
 
Last edited:
  • #18
12,890
9,523
For question ##5## I don't understand the construction. I'd recognise something like ##R[x] / \langle m(x) \rangle ## where the quotient is taken w.r.t the ideal generated by ##m##. But what is ##Z[x] / \langle m(x), n \rangle ##? What is the meaning of the second parameter? What sort of ideal is that?
##\langle a,b \rangle \subseteq R## means the ideal generated by ##a## and ##b##, so (since ##R## is Abelian here): ##\langle a,b \rangle =Ra+Rb\,.## It's simply not a principal ideal, but one generated by two elements. For a non Abelian ring it would be ##\langle a,b \rangle =RaR+RbR\,.##
 
Last edited:
  • Like
Likes nuuskur
  • #19
12,890
9,523
I'll try question 3, looks like something that can be given the ol' modular arithmetic treatment.
Let positive integers ##x,y,z ## satisfy ##x^2+y^2 = z^2 ##. We will show ##60\mid xyz ##.
To this end it suffices to show ##k\mid xyz ## where ##k=3,4,5 ##. It then stands that the least common multiple (which is ##60##) divides the product.

The following is implied by (a.k.a addition in ##Z_n ##)
[tex]
x\equiv a\pmod{n}\ \&\ y\equiv b\pmod{n} \implies x+y\equiv a+b\pmod{n}.
[/tex]

1. It holds that ##x## or ##y## is a multiple of ##3##. Indeed, we have
[tex]
(3k+1)^2 = 9k^2 + 6k + 1 = 3(3k^2+2k)+1\quad\mbox{and}\quad (3k+2)^2 = 9k^2 + 12k +4 = 3(3k^2 + 4k +1) +1
[/tex]
Assuming neither is a multiple of ##3## would mean ##z^2\equiv 2\pmod{3} ## which contradicts the above.

2. At least one factor is divisible by ##4##. We can parametrise
[tex]
x = p^2-q^2\quad y = 2pq\quad z = p^2+q^2,
[/tex]
with ##(p,q)=1##. If ##p## or ##q## is even, we're done. Suppose they are both odd. The square of an odd number is of the form ##4m+1## yielding ##p^2-q^2 \equiv 0\pmod{4} ##.


3. At least one factor is divisible by ##5##. Possible squares modulo ##5## are ##0,1,4##. If none of the factors is a multiple of ##5## then the possibilities for ##x^2+y^2-z^2\pmod{5} ## include (up to commutativity)
[tex]
1+1-1 =1\quad 1+1-4 = 3\quad 1+4-1 = 4\quad 1+4-4 =1\quad 4+4-1 = 2\quad 4+4-4 = 4\quad
[/tex]
none of which is ##0##, contradicting the initial equality.
Well written as on the points. However, I would have liked to read, that for ##4\,|\,xyz## you used the fact that ##2## is prime.
 
  • #20
527
351
It holds that ##Z[x] / \langle p\rangle \cong Z_p[x] ##. This is due to the first isomorphism theorem for rings. Indeed, the mapping ## Z[x]\to Z_p[x],\quad \sum _{n} c_n x^n \mapsto \sum _{n} [c_n] x^n ## is a surjective ring homomorphism annihilated by ##\langle p\rangle##.

So, we're left to show ##Z_5[x] / \langle x^2+2x+4 \rangle \cong Z_5[4+\sqrt{2}] ##. Computing modulo ##x^2+2x+4 ## we get 25? cosets of the form ##[ax + b] , a,b\in Z_5##. Addition and multiplication work modulo 5 as follows
[tex]
[ax+b] + [mx+n] = [(a+m)x + (b+n)]\quad\mbox{and}\quad [ax+b][mx+n] = [(ax+b)(mx+n)] = [ux+v],
[/tex]
where for multiplication one performs long division to determine the coset of the product.

On the other side we got ##Z_5[4+\sqrt{2}] = \{a+b(4+\sqrt{2}) \mid a,b\in Z_5\} ##. Also 25 elements, so this leads to a rather natural looking bijection
[tex]
\varphi : Z_5[x] / \langle x^2+2x+4 \rangle \to Z_5[4+\sqrt{2}],\quad [ax + b] \mapsto b + a(4+\sqrt{2}).
[/tex]
Firstly ##\varphi ([0x +1]) = 1 ## so ##\varphi## preserves the multiplicative identity. Furthermore
[tex]
\varphi ([ax+b] + [mx+n]) = b+n + (a+m)(4+\sqrt{2}) = \varphi ([ax+b]) + \varphi ([mx+n])
[/tex]
Compatibility with multiplication is not so obvious or downright false. To be continued...
 
Last edited:
  • #21
12,890
9,523
It holds that ##Z[x] / \langle p\rangle \cong Z_p[x] ##. This is due to the first isomorphism theorem for rings. Indeed, the mapping ## Z[x]\to Z_p[x],\quad \sum _{n} c_n x^n \mapsto \sum _{n} [c_n] x^n ## is a surjective ring homomorphism annihilated by ##\langle p\rangle##.

So, we're left to show ##Z_5[x] / \langle x^2+2x+4 \rangle \cong Z_5[4+\sqrt{2}] ##.
No. You have shown ##\mathbb{Z}_5[x] \cong \mathbb{Z}[x]/5\mathbb{Z}[x]##, but the argument, why this passes to the quotients ##\mathbb{Z}_5[x]/\langle m(x) \rangle \cong \mathbb{Z}[x]/(5\mathbb{Z}[x]+m(x)\mathbb{Z}[x])## with ##m(x):=x^2+2x+4## is missing.

I think you should at least note that ##\xi := 4+\sqrt{2} \notin \mathbb{Z}_5## because this is important here, and that ##\overline{m}(x):=x^2+2x+4 \in \mathbb{Z}_5[x]## is the minimal polynomial of ##\xi ##. As stated before, not everybody is firm in ring theory.
Computing modulo ##x^2+2x+4 ## we get 25? cosets of the form ##[ax + b] , a,b\in Z_5##

On the other side we got ##Z_5[4+\sqrt{2}] = \{a+b(4+\sqrt{2}) \mid a,b\in Z_5\} ##. Also 25 elements, so this leads to a rather natural looking bijection
[tex]
\varphi : Z_5[x] / \langle x^2+2x+4 \rangle \to Z_5[4+\sqrt{2}],\quad [ax + b] \mapsto b + a(4+\sqrt{2}).
[/tex]
to be continued, I have to power off
 
Last edited:
  • #22
527
351
@fresh_42, you're right the handwavy argument for the initial isomorphism for quotients doesn't quite work.

uh oh, can't edit my last post. At any rate I dusted off some of my ring theory..
it's still a bit handwavy (I omit routine checks), but I did break down the more interesting points
Will often make use of the so called first isomorphism theorem for rings (FITR). Namely the following part.
Given rings ##R,Q## and a surjective homomorphism of rings ##\varphi : R\to Q ##. It holds that ##R/\mbox{ker}\varphi \cong Q##.

Denote ##x^2+2x+4 =: g(x)##.
First, we'll show ##Z[x] / \langle g(x) , p \rangle \cong Z_p[x] / \langle g(x) \rangle ##.
Given ring ##R## and two ideals ##I,J\trianglelefteq R ## it holds that ##I+J## is also an ideal and (more importantly) ##R / (I+J) \cong (R/I) / [J] ## , where ##[J] := \{a + I \mid a\in J\}\trianglelefteq R/I ## is an ideal. Define ##\varphi:R \to (R/I) / [J],\quad r \mapsto (r+I) + [J] ##, which is a surjective homomorphism of rings. Its kernel is ##I+J ##. Now apply FITR.
With that we have
[tex]
Z[x] /\langle g(x), 5\rangle :=Z[x] / (g(x)Z[x] + 5Z[x]) \cong Z_5[x] / g(x)Z_5[x]
[/tex]
-------------------------------------------------------------------------------------------------------------
Given field ##F## and its subfield ##K##, it holds that if ##\beta\in F## is algebraic over ##K## (i.e there is a polynomial in ##K[x]## whose root is ##\beta##) with minimal polynomial ##m(x) ## (if there is one such polynomial, we can certainly pick a minimal one), then ##K[x] / \langle m(x) \rangle \cong K[\beta] ##.
Indeed, define ##\varphi :K[x]\to K[\beta],\quad f\mapsto f(\beta)##. Technically, there is a potential well-definedness issue here i.e ##f(\beta) = \sum _n c_n \beta ^n \overset{?}\in K[\beta]##, but the powers of ##\beta## span the ##K##-vector space ##K[\beta] ##, so that's ok. The degree of minimal polynomial determines the dimension of the vector space.

The mapping ##\varphi ## is a surjective homomorphism of rings. We need to show its kernel is precisely ##\langle m(x)\rangle ##, where ##\langle m(x)\rangle \subseteq \mbox{ker}\varphi## is clear. Conversly, suppose ##\varphi (f) = 0 ## i.e ##f(\beta) = 0##. Since ##m## is a minimal polynomial of ##\beta## it holds that ##m\mid f ## thus ##f\in \langle m(x)\rangle ##. Now apply FITR.

Since ##4+\sqrt{2} =: \beta\notin Z_5## (there can be no linear polynomial in ##Z_5[x] ## with root ##\beta##) and ##g(\beta) =0 ##, ##g## is a minimal polynomial of ##\beta##, thus the isomorphism ##Z_5[x] / \langle g(x)\rangle \cong Z_5[\beta]##.
 
Last edited:
  • #23
ISamson
Gold Member
432
158
@fresh_42 @Greg Bernhardt . I (for my young age) find that these problems are very alien,difficult to me, as I am only in year 8 :) . However, I would really enjoy to take part in a similar challenge, but much easier, like a high school level, however still challenging and interesting for such age. I would propose some type of advanced logic problem, or something with patterns and numbers.
If such possibility is real, I am in. What do you think?
 
  • #24
pbuk
Science Advisor
Gold Member
1,378
372
Problem 9 only needs high school maths.
If the distance from the centre of the pond to the edge is ## r ##, half the distance around the pond is given by ## \pi r ## where the constant ## \pi ## is a bit more than 3.1.

This, plus an understanding of similar triangles (if you stretch a triangle without changing its shape until one side is 4x longer than it started, all the sides are 4x longer than they started).
 
  • #25
527
351
I initially thought P9 to be triangle-solvable, but she doesn't have to swim in a straight line, does she? I haven't looked at the problem in depth, perhaps a winning strategy with involving only straight lines exists for the girl.
 

Related Threads on Basic Math Challenge - August 2018

Replies
20
Views
3K
Replies
63
Views
5K
Replies
62
Views
5K
Replies
82
Views
7K
Replies
38
Views
3K
Replies
121
Views
11K
Replies
67
Views
6K
Replies
175
Views
12K
Replies
71
Views
5K
Replies
16
Views
3K
Top