# Extracurricular Elementary Mathematics Marathon (1 Viewer)

#### Paradoxica

##### -insert title here-
Nice . I actually forgot a term on the LHS from the diophantine equation I was trying to remember though lol, try the edited problem too.

It is slightly harder, but not greatly so. The original hint still stands.

Repost for visibility:

Solve the equation:

$\bg_white x^2+y^2+1=xyz$

over the positive integers.

Hint: Try to determine what z can be first.
$\bg_white \noindent Part 1: Restricting z \\ Suppose (x,x,z) satisfies the equation with z \neq 3. This is impossible, since 2x^2 +1 = zx^2 \Leftrightarrow x^2 (z-2) = 1, which contradicts z\neq 3 So if z \neq 3 then x \neq y. The original equation can be re-arranged to yield (yz -x)^2 +y^2 +1 = (yz -x)yz. So If (x,y,z) is a solution, then (yz -x, y,z) is also a solution to the equation. This is valid, since x(yz -x) = xyz -x^2 = y^2 +1 > 0, which forces yz-x > 0. WLOG, let x>y, so x^2 > y^2 +1 > x(yz-x), which shows x>yz-x. This means that the new solution is smaller than our initial solution. But since x\neq y, this construction of ever smaller solutions can be done indefinitely, so we have an infinite sequence of decreasing positive integers, which is impossible. By Fermat's method of infinite descent, there can be no integer solutions if z \neq 3.$

$\bg_white \noindent Part 2: Constructing solutions \\ By inspection, (1,1) is a solution to x^2 + y^2 + 1 = 3xy. Let (a,b) be a different solution. WLOG, suppose a>b. Exactly like above, rearranging the equation gives us b^2 + (3b-a)^2 + 1 = 3b(3b-a), which gives us a new solution, (b,3b-a). As b\neq 1, we have b^2 -1 > 0, and from the equation, b^2 -1 = a^2 - 3ab + 2b^2 = (a-b)(a-2b)>0, which shows a>2b \Leftrightarrow 3b-a b. It follows that all our infinite solutions can be obtained by applying this recurrence arbitrarily many times.$

$\bg_white \noindent Following this, the solutions are, (1,1), (2,1), (5,2), (13,5), (34,13), (89,34), \cdots and by symmetry, (1,1), (1,2), (2,5), (5,13), (13,34), (34,89), \cdots . The recurrence relation that generates these solutions define the odd-indexed Fibonacci numbers with those exact initial numbers, so the general solutions to the equation are (1,1),(F_{2n-1},F_{2n+1}),(F_{2n+1},F_{2n-1}) \; \; \forall n \in \mathbb{N}$

Last edited:

#### seanieg89

##### Well-Known Member
$\bg_white \noindent Part 1: Restricting z \\ Suppose (x,x,z) satisfies the equation with z \neq 3. This is impossible, since 2x^2 +1 = zx^2 \Leftrightarrow x^2 (z-2) = 1, which contradicts z\neq 3 So if z \neq 3 then x \neq y. The original equation can be re-arranged to yield (yz -x)^2 +y^2 +1 = (yz -x)yz. So If (x,y,z) is a solution, then (yz -x, y,z) is also a solution to the equation. This is valid, since x(yz -x) = xyz -x^2 = y^2 +1 > 0, which forces yz-x > 0. WLOG, let x>y, so x^2 > y^2 +1 > x(yz-x), which shows x>yz-x. This means that the new solution is smaller than our initial solution. But since x\neq y, this construction of ever smaller solutions can be done indefinitely, so we have an infinite sequence of decreasing positive integers, which is impossible. By Fermat's method of infinite descent, there can be no integer solutions if z \neq 3.$

$\bg_white \noindent Part 2: Constructing solutions \\ By inspection, (1,1) is a solution to x^2 + y^2 + 1 = 3xy. Let (a,b) be a different solution. WLOG, suppose a>b. Exactly like above, rearranging the equation gives us b^2 + (3b-a)^2 + 1 = 3b(3b-a), which gives us a new solution, (b,3b-a). As b\neq 1, we have b^2 -1 > 0, and from the equation, b^2 -1 = a^2 - 3ab + 2b^2 = (a-b)(a-2b)>0, which shows a>2b \Leftrightarrow 3b-a b. It follows that all our infinite solutions can be obtained by applying this recurrence arbitrarily many times.$

$\bg_white \noindent Following this, the solutions are, (1,1), (2,1), (5,2), (13,5), (34,13), (89,34), \cdots and by symmetry, (1,1), (1,2), (2,5), (5,13), (13,34), (34,89), \cdots . The recurrence relation that generates these solutions define the odd-indexed Fibonacci numbers with those exact initial numbers, so the general solutions to the equation are (1,1),(F_{2n-1},F_{2n+1}),(F_{2n+1},F_{2n-1}) \; \; \forall n \in \mathbb{N}$
Well done .

#### Blast1

##### New Member
Trivial for n=1.

Suppose the property holds for 1..n-1.

For general n, if their sum is divisible by n, then their sum mod n is 0. Take all elements mod n. If all elements mod n are 0, pick any subset. Otherwise, pick out an element x mod N which is nonzero mod n. 0 <= x < n. Of the remaining elements, take any n-x > 0 elements. These n-x elements have a subset divisible by n-x, so if we then add x to the subset, we have a subset with sum (n-x) + x = 0 mod N, so the subset is divisible by n.
I don't think this is quite right? Just because the sum of a subset is divisible by n-x, it doesn't necessarily mean that the sum is n-x mod N? Or have I misinterpreted what you're saying?

Here's what I had. Suppose that a_i are the elements of the set. Now, consider the sums b_i=a_1+a_2+....+a_i. If one of b_1,b_2.. b_n is 0 mod n, that set has sum divisible by n. If not, then by the pigeon hole principle, two of these are of the same class mod n. Suppose that these two are b_m and b_n, (n>m). Then, b_n-b_m has 0 mod n.

$\bg_white \noindent Show that in any arbitrarily long sub-interval of the natural numbers, there exists a sub-interval containing no prime numbers.\\Hence, show that in any sub-interval of n elements, there will always be a sub-interval containing k prime numbers for all \pi(n) > k > 0, where \pi(n) is the prime counting function, which denotes the number of primes less than or equal to n.$

$\bg_white \noindent Discrete Intermediate Value Theorem: \\ For all \{a,b\} \in \mathbb{Z}, \; a
I think we need a bit of clarification here, \pi (3)= 2, but we can definitely have subintervals of length 3 which contain no prime numbers. For instance 20,21,22 is such an interval, and none of the three are prime numbers.

Last edited:

#### Blast1

##### New Member
Yes, there can be sub-intervals of length "n" with no prime numbers. however, you must prove this for all n.

And the second part is less straightforward, but still doable. The upper bound is always pi(n), because that is the maximum number of prime numbers in any sub-interval of the natural numbers of length n
?

In my previous post, I was addressing the second part of your question, not the first (I suppose I should've mentioned this). Basically, in your question you claim that if we have a subinterval of length n (has n elements), then there must exist a subinterval containing k primes for all k which exceeds 0 but is bounded by pi(x). In my previous post, I provided a counter example to this claim, showing how there exists a subinterval of length 3, but within the subinterval which I specifically mentioned (20,21,22) there is no subinterval which contains any primes. According to your question, within the subinterval (20,21,22), there should exist a subinterval which contains 1 prime and also another subinterval which contains 2 primes. Obviously, that's not true in this example.

Also, the first part of your question doesn't quite make sense either. For instance, the elements 2 and 3 form a subinterval of length 2, and clearly any subinterval within this subinterval must contain a prime. Thus your claim is false.

So this is why I'm asking for a clarification, as the question in its current wording isn't true.

Last edited:

#### Paradoxica

##### -insert title here-
$\bg_white \noindent Show that there exist arbitrarily long sub-intervals of the natural numbers that contain no primes.\\Hence, show that amongst the natural numbers, there will always be a sub-interval of length n containing k prime numbers for all \pi(n) \geq k \geq 0, where \pi(n) is the prime counting function, which denotes the number of primes in the interval (1,n).$

$\bg_white \noindent Discrete Intermediate Value Theorem: \\ For all \{a,b\} \in \mathbb{Z}, \; azz

#### seanieg89

##### Well-Known Member
$\bg_white First, we look at the second assertion. The number of primes in the set I_n(x)=\{x+1,x+2,\ldots,x+n\} is given by g_n(x):=\pi(x+n)-\pi(x) for any non-negative integer x.\\ \\ If we look at the shifted interval I_n(x+1) instead, we might lose a prime from no longer having x+1 in our set, and we might gain a prime from adding x+n+1 to our set. \\ \\It might also be the case that both or neither of these things happen. In any case, the main point is that g_n(x+1)-g_n(x) can either be 0,-1 or 1. Ie the function g_n(x) takes steps of size at most 1. \\ \\ By the discrete intermediate value theorem, it then suffices to show that for each n, we can find an x_n with g_n(x_n)=0 (as we trivially have g(0)=\pi(n), so every integer between 0 and \pi(n) must then lie in the range of g.)\\ \\ Proving this fact also establishes the first assertion, so we can now kill these two birds with the one stone next post.$

#### seanieg89

##### Well-Known Member
(It suffices to show that pi(x)=o(x), which is a quite weak statement about the distribution of the primes that can be proved by a completely elementary sieving process. Am just thinking of the cleanest way to write this. Will post shortly.)

#### Paradoxica

##### -insert title here-
$\bg_white First, we look at the second assertion. The number of primes in the set I_n(x)=\{x+1,x+2,\ldots,x+n\} is given by g_n(x):=\pi(x+n)-\pi(x) for any non-negative integer x.\\ \\ If we look at the shifted interval I_n(x+1) instead, we might lose a prime from no longer having x+1 in our set, and we might gain a prime from adding x+n+1 to our set. \\ \\It might also be the case that both or neither of these things happen. In any case, the main point is that g_n(x+1)-g_n(x) can either be 0,-1 or 1. Ie the function g_n(x) takes steps of size at most 1. \\ \\ By the discrete intermediate value theorem, it then suffices to show that for each n, we can find an x_n with g_n(x_n)=0 (as we trivially have g(0)=\pi(n), so every integer between 0 and \pi(n) must then lie in the range of g.)\\ \\ Proving this fact also establishes the first assertion, so we can now kill these two birds with the one stone next post.$
Ahh yes, that was the other way to do it, but that was meant to be the second part to the problem. My intended solution was to use the fact that n! has n-1 obvious factors, and exploit that to construct an arithmetic progression strictly consisting of composite numbers, which is a lot easier to prove.

#### seanieg89

##### Well-Known Member
(It suffices to show that pi(x)=o(x), which is a quite weak statement about the distribution of the primes that can be proved by a completely elementary sieving process. Am just thinking of the cleanest way to write this. Will post shortly.)
$\bg_white Let S_p be the set of natural numbers indivisible by p. \\ \\ It is trivial that \frac{|S_p\cap [1,n]|}{n}\rightarrow 1-\frac{1}{p} as n\rightarrow\infty.\\ \\ Moreover, since primes are pairwise coprime, we have \frac{|(\cap_{k=1}^m S_{p_k})\cap [1,n]|}{n}\rightarrow \prod_{k=1}^m \left(1-\frac{1}{p_k}\right).\\ \\ As this quantity for a given m is telling us the proportion of numbers that are indivisible by any of the first m primes, in the limit as n\rightarrow\infty this gives us an m-dependent upper bound for the proportion of primes.$

$\bg_white However:\\ \\\prod_{k=1}^m \left(1-\frac{1}{p_k}\right)=\prod_{k=1}^m \left(\sum_{j=0}^\infty \frac{1}{p_k^j}\right)^{-1}=\left(\sum_n \frac{1}{n}\right)^{-1}\\ \\ where the final summation is taken over all n whose only prime factors lie in the set \{p_1,\ldots,p_m\}. By the divergence of the harmonic series, we can make this quantity arbitrarily small by taking m sufficiently large.\\ \\ In other words, the proportion of the first n positive integers that are prime must tend to zero.$

$\bg_white Now if for some m, every collection of m consecutive integers contained a prime, that would imply that the proportion of primes in the first n positive integers would have to be at least 1/m in the limit n\rightarrow\infty. This is impossible by what we just proved, and hence we are done.$

#### seanieg89

##### Well-Known Member
(And yes, this is strictly more work than one needs to do to answer your original question, where a construction using a factorial explicitly gives us prime gaps of length blah. I just did it this way because I personally wanted to see how "low-tech" I could make a proof of the fact that the primes have density zero. )

Stronger statements about prime distribution are also very much within the scope of MX2 level techniques.

One such example is Bertrand's postulate, which states that there is at least one prime strictly between n and 2n for any positive integer n greater than 1.

This will be harder for a HS student to do without guidance, but I encourage any interested student to think about it / have a crack at it.

Last edited:

#### Paradoxica

##### -insert title here-
$\bg_white \noindent Solve completely over \mathbb{N} . \\a) y^2 = (x-2)2^{x-1}+1 \\ b) y^2 = (x-1)2^x+1$

#### Paradoxica

##### -insert title here-
$\bg_white \noindent Here's a set of simpler problems, all doable with infinite descent: \\ Note: all solutions must be in \mathbb{N} \\ a^2 + b^2 = 3c^2 \\ x^3 +2y^3 = 4z^3 \\Simultaneous Equations: a^2 + 6b^2 = p^2 and b^2 + 6a^2 = q^2$

#### Blast1

##### New Member
$\bg_white \noindent Show that there exist arbitrarily long sub-intervals of the natural numbers that contain no primes.\\Hence, show that amongst the natural numbers, there will always be a sub-interval of length n containing k prime numbers for all \pi(n) \geq k \geq 0, where \pi(n) is the prime counting function, which denotes the number of primes in the interval (1,n).$
$\bg_white \noindent Discrete Intermediate Value Theorem: \\ For all \{a,b\} \in \mathbb{Z}, \; azz
This wording means that the question is now valid, before you said that any subinterval of length n contained a subinterval of k primes (pi(x)>k>0), which was clearly not true and hence I was confused. I would normally post my solution, but Seanieg89 has already done so and mine was pretty similar except in the part where you had to prove that there exists a subinterval with 0 primes.

$\bg_white \noindent Solve completely over \mathbb{N} . \\a) y^2 = (x-2)2^{x-1}+1 \\ b) y^2 = (x-1)2^x+1$
$\bg_white Part a). Testing x =1\rightarrow5, we obtain (x,y): (2,+-1), (5,+-7) (0 isn't natural number).\\(y+1)(y-1)=y^2-1=(x-2)2^{x-1}\ So, the the RHS has two factors which differ by 2 \Rightarrow |2^ac-2^bd|=2 \ where a+b=x-1 and cd=x-2.a,b,c,d all natural. |2^{a-1}c-2^{b-1}d|=1. a,b cannot both exceed 1(RHS is odd) so we consider 2 cases. Case 1: a=1 and b\geq1. Then, |\frac{x-2}{d}-2^{x-3}d|=1 \Rightarrow \ x-2-2^{x-3}d= \pm d. \\ x-2=2^{x-3}d^2 \pm d. But for x>5, RHS \geq 2^{x-3} \pm 1>2^{x-3}-1.>x-2, contradiction. (Last inequality from calculus) Case 2: a=0, b\geq0. By following a similar method as case 1, we reach: 2^{x-1}d^2 \pm d=x-2. But for x>3 LHS> 2^{x-1}-1>x-2, contradiction. By symmetry, we've dealt with the cases where b=0 and a\geq0, or b=1 and a\geq1. Thus, no solution exists for x>5, and so our solution set is (x,y): (2,+-1), (5,+-7) \\ Part b) is part a with all the x solutions dropped by 1, so we now have (1,+-1), (4,+-7).$

Last edited:

#### Blast1

##### New Member
$\bg_white \noindent Here's a set of simpler problems, all doable with infinite descent: \\ Note: all solutions must be in \mathbb{N} \\ a^2 + b^2 = 3c^2 \\ x^3 +2y^3 = 4z^3 \\Simultaneous Equations: a^2 + 6b^2 = p^2 and b^2 + 6a^2 = q^2$
$\bg_white a^2+b^2=3c^2. Suppose there exists a natural solution (a,b,c) to this. Since the quadratic residue mod 3 is 0 or 1, the equation can only hold if a and b are both divisible by 3 (otherwise LHS would be 1 or 2 mod 3 whilst the RHS is 0 mod 3). So, a=3k, b=3j, c=3l, 9k^2+9j^2=3(9l^2). Dividing through by 9, we find that (k,j,l) is a smaller natural solution. By Fermat's method of descent, there are no natural solutions. \\ x^3+2y^3=4z^3. Similar to first q, 2|x, and thus 2|y as 4|RHS and x^3 is even. But since the LHS is then divisible by 8, so is the RHS, so 2|z. (\frac{x}{2},\frac{y}{2}, \frac{z}{2}) is a smaller natural solution, and thus there are no natural solutions. \\ Adding both equations, 7(a^2+b^2)=p^2+q^2. Since the quadratic residue of 7 is 0,1,2,4, and the LHS is 0 mod7, 7 must divide both p and q. This implies that 7|a,b so (a/7,b/7,p/7,q/7) is a smaller natural solution, so no natural solutions exist.$

Last edited:

#### Paradoxica

##### -insert title here-
$\bg_white a^2+b^2=3c^2. Suppose there exists a natural solution (a,b,c) to this. Since the quadratic residue mod 3 is 0 or 1, the equation can only hold if a and b are both divisible by 3 (otherwise LHS would be 1 or 2 mod 3 whilst the RHS is 0 mod 3). So, a=3k, b=3j, c=3l, 9k^2+9j^2=3(9l^2). Dividing through by 9, we find that (k,j,l) is a smaller natural solution. By Fermat's method of descent, there are no natural solutions. \\ x^3+2y^3=4z^3. Similar to first q, 2|x, and thus 2|y as 4|RHS and x^3 is even. But since the LHS is then divisible by 8, so is the RHS, so 2|z. (\frac{x}{2},\frac{y}{2}, \frac{z}{2}) is a smaller natural solution, and thus there are no natural solutions. \\ Adding both equations, 7(a^2+b^2)=p^2+q^2. Since the quadratic residue of 7 is 0,1,2,4, and the LHS is 0 mod7, 7 must divide both p and q. This implies that 7|a,b so (a/7,b/7,p/7,q/7) is a smaller natural solution, so no natural solutions exist.$
You've solved a lot of problems, maybe post your own?

#### seanieg89

##### Well-Known Member
A bit on the easier side, but just to get the ball rolling in this thread again:

A function g(n) defined on the non-negative integers satisfies:

i) g(0)=g(1)=0.

ii) g(p)=1 if p is prime.

iii) g(mn)=m*g(n)+n*g(m) for all non-negative integers m and n.

Find all n such that g(n)=n.

---------------------------------------

A somewhat harder followup question is proving that the sequence obtained by:

u(0)=63
u(n+1)=g(u(n))

tends to infinity.

Last edited:

#### Paradoxica

##### -insert title here-
A bit on the easier side, but just to get the ball rolling in this thread again:

A function g(n) defined on the non-negative integers satisfies:

i) g(0)=g(1)=0.

ii) g(p)=1 if p is prime.

iii) g(mn)=m*g(n)+n*g(m) for all non-negative integers m and n.

Find all n such that g(n)=n.

---------------------------------------

A somewhat harder followup question is proving that the sequence obtained by:

u(0)=63
u(n+1)=g(u(n))

tends to infinity.
Ahh, arithmetic derivative, I have not seen you in a while.

I'll work on this later today if I get time. Otherwise, someone else can do it.

#### Paradoxica

##### -insert title here-
$\bg_white The problem amounts to solving the infinite diophantine equation:$

$\bg_white \frac{a_1}{2}+\frac{a_2}{3}+\frac{a_3}{5}+\frac{a_4}{7}+\frac{a_5}{11}+\frac{a_6}{13}+\frac{a_7}{17}+\frac{a_8}{19}+\cdots+\frac{a_k}{p_k}+\cdots = 1$

$\bg_white Over the naturals.$

$\bg_white Which I'm not sure is any easier or harder. I think it's harder.$

$\bg_white A trivial class of solutions is p_k^{p_k}$

$\bg_white p_k is the k^{\text{th}} prime number.$

$\bg_white Anyone else got any ideas?$

Last edited:

#### Paradoxica

##### -insert title here-
$\bg_white \noindent Suppose u_n = 2^4*k for some integer k. Applying the so-called arithmetic derivative, we have u_{n+1} =2^4(2k+k')>2^5*k. This shows that each term, is strictly at least twice as large as the previous term. u_5 is the first term to contain a fourth power of two, and hence, this sequence diverges into infinity.$

#### seanieg89

##### Well-Known Member
$\bg_white \noindent Suppose u_n = 2^4*k for some integer k. Applying the so-called arithmetic derivative, we have u_{n+1} =2^4(2k+k')>2^5*k. This shows that each term, is strictly at least twice as large as the previous term. u_5 is the first term to contain a fourth power of two, and hence, this sequence diverges into infinity.$
Good, you have done the harder part of the question .

It remains to determine the exact solutions of g(x)=x but you are super close.