Number of times to do Euclidean GCD.

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Number of times to do Euclidean GCD.

G H J

Reveal topic tags

Euclidean algorithm

L

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2017 N8

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1594 posts

#1 h Jul 10, 2018, 11:21 AM • 9 Y

Y by Muradjl, rkm0959, Amir Hossein, GammaBetaAlpha, megarnie, mathleticguyyy, rama1728, Adventure10, Mango247

Let $p$ be an odd prime number and $\mathbb{Z}_{>0}$ be the set of positive integers. Suppose that a function $f:\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}\to\{0,1\}$ satisfies the following properties:

$f(1,1)=0$ .
$f(a,b)+f(b,a)=1$ for any pair of relatively prime positive integers $(a,b)$ not both equal to 1;
$f(a+b,b)=f(a,b)$ for any pair of relatively prime positive integers $(a,b)$ .

Prove that
$\sum_{n=1}^{p-1}f(n^2,p) \geqslant \sqrt{2p}-2.$

This post has been edited 4 times. Last edited by MarkBcc168, Feb 8, 2020, 2:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1721 posts

#2 h Jul 10, 2018, 11:49 AM • 3 Y

Y by megarnie, Adventure10, Mango247

TST #3, really difficult problem, but one idea is enough to kill the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

322 posts

#3 h Jul 10, 2018, 11:53 AM • 3 Y

Y by rkm0959, Adventure10, Mango247

We shall prove that for any two coprime integers $a$ and $b$ , $f(a, b) = 1$ if and only if the inverse of $a$ modulo $b$ , taken in the set $\{1, 2, \dots, b\}$ , is less than or equal to $\frac{b}{2}$ . We first prove that the given conditions uniquely define $f$ over the pairs of coprime integers. Starting with a pair of coprime integers $(a, b)$ , if $a > b$ then consider the pair $(a - b, b)$ , and if $b > a$ then consider the pair $(b, a)$ . Any of this transformations gives another pair of coprime positive integers, and we can check that the value of $a + 2b$ decreases. Thus eventually we obtain the pair $(1, 1)$ . Moreover, by reversing this process, all of the operations have the forms $(x, y) \to (x + y, y)$ or $(x, y) \to (y, x)$ , so the value of $f$ for each pair can be computed from the next pair in the sequence. Thus indeed the function is uniquely defined.

It now suffices to prove that the function $g$ that satisfies $g(a, b) = 1$ if and only if the inverse of $a \pmod{b}$ is at most $b$ also satisfies the conditions of the problem. Clearly $g(1, 1) = 0$ , so this one holds. Additionally, $g(a + b, b) = g(a, b)$ holds because $a$ and $a + b$ are congruent modulo $b$ , so they have the same inverse.

Finally we show that $g(a, b) + g(b, a) = 1$ whenever $a, b$ are not both equal to $1$ . Let $a^{-1}$ be the inverse of $a \pmod{b}$ taken in $1, 2, \dots, b$ , then there exists some integer $x$ such that $aa^{-1} + bx = 1$ . Now let $b^{-1}$ be the inverse of $b \pmod{a}$ taken in $1, 2, \dots, a$ , and let $x = ak + i$ where $1 \leq i \leq a$ . Taking the expression $aa^{-1} + abk + bi = 1$ modulo $a$ we find that $bi \equiv 1 \pmod{a}$ and therefore $i = b^{-1}$ . We now have

$aa^{-1} + bb^{-1} + kab = 1 \implies aa^{-1} + bb^{-1} \equiv 1 \pmod{ab}$
Now assume that both $1 \leq a^{-1} \leq \frac{b}{2}$ and $1 \leq b^{-1} \leq \frac{a}{2}$ . Then $a + b \leq aa^{-1} + bb^{-1} \leq ab$ . But because $a + b \geq 2$ it is impossible for this expression to be congruent to $1 \pmod{ab}$ . Assume now that both $\frac{a}{2} < b^{-1} \leq a$ and $\frac{b}{2} < a^{-1} \leq b$ . Then $b^{-1} \geq \frac{a + 1}{2}$ and $a^{-1} \geq \frac{b + 1}{2}$ . These two inequalities now imply that $ab + \frac{a + b}{2} \leq aa^{-1} + bb^{-1} \leq 2ab$ , so now because $a + b > 2$ , as $a$ and $b$ are not both $1$ , we once again find that it's impossible for this expression to be congruent to $1$ modulo $ab$ . These two analyses together imply that $g(a, b) \neq g(b, a)$ , and therefore $g(a, b) + g(b, a) = 1$ . It follows that indeed $g = f$ .

Finally we compute the desired sum. We have $f(n^2, p) = 1$ if and only if the inverse of $n^2$ is less than or equal to $\frac{p - 1}{2}$ . Thus the sum is equal to the number of values of $n$ such that $n^{-2} \pmod{p}$ is at most $\frac{p - 1}{2}$ . Moreover $k^{-2} \equiv (p - k)^{-2} \pmod{p}$ , so the total sum is twice of the sum that only includes $n = 1, 2, \dots, \frac{p - 1}{2}$ . Now, because

$\left\{1^2, 2^2, \dots, \left(\frac{p - 1}{2}\right)^2\right\} \equiv \left\{1^{-2}, 2^{-2}, \dots, \left(\frac{p - 1}{2}\right)^{-2}\right\} \pmod{p}$
The required sum is equal to twice the number of quadratic residues that lie in the interval $\left[1, \frac{p - 1}{2}\right]$ . The bound in the problem now follows trivially from noticing that there are at least $\sqrt{\frac{p}{2}} - 1$ perfect squares in this interval, because $\frac{p}{2}$ is not a square.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1721 posts

#4 h Jul 10, 2018, 12:03 PM • 2 Y

Y by Adventure10, Mango247

Indeed, the lemma is a killer one...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6870 posts

#5 h Jul 10, 2018, 12:50 PM • 8 Y

Y by TYT, smurfcc, mijail, v4913, HamstPan38825, Kingsbane2139, Adventure10, yofro

Incredibly, we have the following description of $f$ .

Lemma: For any relatively prime $(a,b) \ne (1,1)$ , $f(a,b) = \begin{cases} 1 & (a^{-1} \bmod b) \le b/2 \\ 0 & (a^{-1} \bmod b) > b/2. \end{cases}$
We give the short self-contained induction proof for now; see the remarks for a more reasonable and motivated proof.

Proof. [Inductive proof by Ankan Bhattacharya] It is enough to show that if $a, b > 1$ are relatively prime then $a^{-1} \pmod{b} \le b/2$ iff $b^{-1} \pmod{a} > a/2$ . Let $(x, y)$ be a minimal positive integer pair with $ax - by = 1$ . Then $x \le b - 1$ , $y \le a - 1$ , and $\begin{align*} a^{-1} & \equiv x \pmod{b} \\ b^{-1} & \equiv a - y \pmod{a}. \end{align*}$ Thus $a^{-1} \pmod{b} = x$ , $b^{-1} \pmod{a} = a - y$ . Finally $x \le b/2 \iff ax \le ab/2 \iff by < ab/2 \iff y < a/2 \iff a - y > a/2.$ $\blacksquare$

In particular, for any $n$ such that $n \equiv \pm 1/k \pmod p$ with $k \in \{1, \dots, \left\lfloor \sqrt{p/2} \right\rfloor \}$ , we have $f(n^2,p) = 1$ , so this implies the result.

Remark: In general, we have $f(a,p) = 1-f(p,a) = 1-f(p-a,a) = f(a,p-a) = f(p,p-a) = 1-f(p-a,p)$ and so $f(a,p) + f(p-a, p) = 1$ .

Note that if $p \equiv 1 \pmod 4$ , this already solves the problem. If $r$ is any quadratic residue, so is $-r$ , and accordingly $f(-r,p) + f(r,p) = 1$ ; so we have actually $\sum_n f(n^2, p) = \frac{1}{2} (p-1) \qquad \forall p \equiv 1 \pmod 4.$

Remark: In fact, it is true far that for $p \equiv 3 \pmod 4$ , the number of quadratic residues in $[1,p/2]$ is more than the number in $[p/2,p-1]$ , and hence the $\frac{1}{2}(p-1)$ is actually sharp.

Indeed, from https://en.wikipedia.org/wiki/Quadratic_residue#Dirichlet.27s_formulas: if one defines the Dirichlet $L$ -function $L(s) = \sum_n \left( \frac np \right) n^{-s}$ then $L(1) = \frac{\pi}{\left( 2 - \left( \frac 2p \right) \right) \sqrt p} \sum_{n=1}^{\frac{p-1}{2}} > 0$ which is the result we wanted. It seems no elementary proof is known.

Remark: [Yang Liu] The key lemma in the problem seems to come out of nowhere. Here is how you can come up with it.

Denote by $\operatorname{GL}_2({\mathbb Z})$ the set of $2 \times 2$ integer matrices with determinant $\pm 1$ . Suppose we consider only coprime pairs $(a,b)$ with $a \ge b \ge 0$ .

Consider first running the Euclidean algorithm backwards; starting from $(1,0)$ and trying to reach a given pair. An any point we can go from $(a,b) \to (a+b,b)$ or $(a,b) \to (a+b,a)$ ; the latter operation involves a switch and we're trying to count the parity of switches. (We don't count $(1,1) \to (2,1)$ as a switch.) If we interpret our pair as a column vector $\begin{bmatrix} a \\ b \end{bmatrix}$ , then this means we are multiplying by either multiplying by $T = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ or $S = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ (for ``switch''), one after another, several times. (For experts, I think $T$ and $S$ generate $\operatorname{GL}_2({\mathbb Z})$ .) As an example, to reach $(18,7)$ from $(1,0)$ we do $\begin{align*} \begin{bmatrix} 1 \\ 0 \end{bmatrix} &\xrightarrow{\times S} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \xrightarrow{\times T} \begin{bmatrix} 2 \\ 1 \end{bmatrix} \xrightarrow{\times T} \begin{bmatrix} 3 \\ 1 \end{bmatrix} \xrightarrow{\times S} \begin{bmatrix} 4 \\ 3 \end{bmatrix} \\ &\xrightarrow{\times S} \begin{bmatrix} 7 \\ 4 \end{bmatrix} \xrightarrow{\times S} \begin{bmatrix} 11 \\ 7 \end{bmatrix} \xrightarrow{\times T} \begin{bmatrix} 18 \\ 7 \end{bmatrix}. \end{align*}$ The punch line is that the overall matrix $M$ we have is one whose first column is $\begin{bmatrix} a \\ b \end{bmatrix}$ , and we want to count the number of times we used the matrix $S$ . But $\det T = +1$ and $\det S = -1$ , so this is given by the sign of $\det M \in \{\pm 1\}$ , as we wanted!

Going forwards again, the idea is that given $\begin{bmatrix} a \\ b \end{bmatrix}$ that we are processing with the Euclidean algorithm, we can annotate by completing it to a $2 \times 2$ matrix in $\operatorname{GL}_2({\mathbb Z})$ with nonnegative entries, such that the first row exceeds the second row. As an example, for $(a,b) = (18,7)$ the process goes $(18,7) \to (7,4) \to (4,3) \to (3,1) \to (1,0)$ , and the set of accompanying annotated matrices is $\begin{bmatrix} 18 & 5 \\ 7 & 2 \end{bmatrix} \to \begin{bmatrix} 7 & 2 \\ 4 & 1 \end{bmatrix} \to \begin{bmatrix} 4 & 1 \\ 3 & 1 \end{bmatrix} \to \begin{bmatrix} 3 & 1 \\ 1 & 0 \end{bmatrix} \to \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}.$ Each steps corresponds to doing row reductions and then swapping rows; the determinant flips sign at every switch. The left column contains the actual $(a,b)$ that are being processed while the right column contains the suitable inverses.

Thus the sign of the determinant of the initial matrix, when populated with nonnegative entries, determines the eventual parity. Essentially, there is a unique nonnegative pair of integers $(x,y)$ for which $ax + by = \pm 1$ and $x \ge y$ . Note here $x \equiv a ^{-1} \pmod b$ . In any case, one merely unravels the condition until the key lemma falls out.

This post has been edited 1 time. Last edited by v_Enhance, Aug 21, 2018, 2:43 AM
Reason: colorize

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7579 posts

ZetaX

#6 h Jul 10, 2018, 2:04 PM • 4 Y

Y by USJL, gvole, Adventure10, Mango247

A quick remark: one can show by non-elementary means that the sum is bounded below by $\frac{p-1}{2}$ , which is sharp iff $p \equiv 1 \mod 4$ . In the other half of cases, the difference can be described by the class number of the imaginary quadratic field of discriminant $-p$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

535 posts

USJL

#7 h Jul 10, 2018, 3:16 PM • 3 Y

Y by pavel kozlov, Adventure10, GeoKing

v_Enhance wrote:

Remark: [Yang Liu] The key lemma in the problem seems to come out of nowhere.

Here is how I came up with the key lemma:
$f(a,b)=1$ if and only if the length of the continued fraction (without an ending $1$ ) of $a/b$ is odd. The parity of the length leads me to consider the difference of the continued fractions. Suppose that after truncating the last term the continued fraction becomes $c/d$ , then we have
$ad-bc = (-1)^{f(a,b)-1}.$ If we instead only decrease the last term by $1$ and get $c'/d'$ , then
$ad'-bc' = (-1)^{f(a,b)}.$ It is clear that $d\leq d'<b$ , and so the lemma follows immediately.

This post has been edited 2 times. Last edited by USJL, Jul 10, 2018, 3:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#8 h Sep 13, 2019, 9:36 PM • 3 Y

Y by HolyMath, smurfcc, Adventure10

This solution is based on the ideas given in Yang Liu's remark found at the end of post #5.

The conditions of the problem imply that
$f(a,b)=f(a+b,b)=1-f(a+b,a).$ As in the remark, we apply the Euclidean algorithm backwards, starting from $(1,0)$ and stopping at $(a,b)$ , using the operations $(a,b)\mapsto(a+b,b)$ and $(a,b)\mapsto(a+b,a)$ (it is very important that the operation $(1,1)\mapsto(2,1)$ is viewed as coming from the first type). Note that this only works if $a\ge b$ . Viewing the pairs as vectors $\begin{bmatrix}a\\b\end{bmatrix}$ , we see that the first operation is analogous to multiplication by the matrix $T=\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ and the second is multiplication by $S=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ .

We'll use the same example as that of Yang Liu. We can get the pair $(18,7)$ from $(1,0)$ by doing
$\begin{align*} \begin{bmatrix} 1 \\ 0 \end{bmatrix} &\xrightarrow{\times S} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \xrightarrow{\times T} \begin{bmatrix} 2 \\ 1 \end{bmatrix} \xrightarrow{\times T} \begin{bmatrix} 3 \\ 1 \end{bmatrix} \xrightarrow{\times S} \begin{bmatrix} 4 \\ 3 \end{bmatrix} \\ &\xrightarrow{\times S} \begin{bmatrix} 7 \\ 4 \end{bmatrix} \xrightarrow{\times S} \begin{bmatrix} 11 \\ 7 \end{bmatrix} \xrightarrow{\times T} \begin{bmatrix} 18 \\ 7 \end{bmatrix}, \end{align*}$ or
$\begin{bmatrix} 18 \\ 7 \end{bmatrix} = TSSSTTS\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ Each application of $S$ flips the value of $f$ , so our goal is to count the parity of the number of times that $S$ is used in this chain (this is why it is important to view $(1,1)\mapsto(2,1)$ as an application of $T$ not $S$ ). The key idea here is that $\det T=1$ and $\det S=-1$ , so letting the algorithm matrix be $M$ (here $M=TSSSTTS$ ), we see that $f(a,b)=1$ if and only if $\det M=1$ (note that we effectively have $f(1,0)=1$ since $(1,0)\mapsto(1,1)$ is an application of $S$ ).

The issue here is that we currently only have the first column of $M$ , which is $\begin{bmatrix}a\\b\end{bmatrix}$ . To get the second column, we need to find what $M$ does to $(0,1)$ . Note that for any nontrivial pair $(a,b)$ , our first two operations on $(1,0)$ have to be a $T$ followed by an $S$ , or
$ST=\begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix}.$ At this point, we have the observation that our matrix is of the form $\begin{bmatrix} p & r \\ q & s \end{bmatrix}$ where $p\ge q\ge 0$ , $r\ge s\ge 0$ , $p\ge 2q$ , and $r\ge 2s$ . It is not too hard to see that applying $S$ or $T$ to a matrix of this form keeps it in this form, so our final matrix $M$ is of the form $\begin{bmatrix}a & x\\b & y\end{bmatrix}$ where $a\ge b\ge 0$ , $x\ge y\ge 0$ , $a\ge 2x$ , $b\ge 2y$ , and $\det M=\pm 1$ .

Pick integers $u$ and $v$ such that $au-bv=1$ . Note that $u\equiv a^{-1}\pmod{b}$ and $v\equiv a^{-1}\pmod{a}$ . If $\det M=1$ , then our final matrix is of the form $\begin{bmatrix}a & v+ak \\ b & u+bk\end{bmatrix}$ . To ensure that $b\ge 2u+2bk$ , or $0\le u+bk\le b/2$ , we need $(a^{-1}\pmod{b})\le b/2$ . Similarly, if $\det M=-1$ , then $(a^{-1}\pmod{b})>b/2$ , so we have
$f(a,b) = \begin{cases} 1 & (a^{-1} \bmod b) \le b/2 \\ 0 & (a^{-1} \bmod b) > b/2. \end{cases}$ From here, the solution is very easy. Note that $f(a,b)=f(a\pmod{b},b)$ , so
$\sum_{n=1}^{p-1}f(n^2,p)=\sum_{m=1}^{p-1}f(m^{-2}\pmod{p},p).$ Note that for $m\in\left\{\pm 1,\ldots,\pm\left\lfloor\sqrt{p/2}\right\rfloor\right\}$ , we have $m^2\pmod{p}\le p/2$ , so the sum is at least $2\lfloor\sqrt{p/2}\rfloor\ge\sqrt{2p}-2$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3 posts

Roct-7

#9 h Feb 8, 2020, 1:15 PM • 2 Y

Y by Adventure10, Mango247

USJL wrote:

v_Enhance wrote:

Remark: [Yang Liu] The key lemma in the problem seems to come out of nowhere.

Here is how I came up with the key lemma:
$f(a,b)=1$ if and only if the length of the continued fraction (without an ending $1$ ) of $a/b$ is odd. The parity of the length leads me to consider the difference of the continued fractions. Suppose that after truncating the last term the continued fraction becomes $c/d$ , then we have
$ad-bc = (-1)^{f(a,b)-1}.$ If we instead only decrease the last term by $1$ and get $c'/d'$ , then
$ad'-bc' = (-1)^{f(a,b)}.$ It is clear that $d\leq d'<b$ , and so the lemma follows immediately.

You didn't prove b/2 is greater than d, how do you prove the lemma?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

535 posts

USJL

#10 h Mar 28, 2020, 1:18 PM

Y by

Roct-7 wrote:

USJL wrote:

v_Enhance wrote:

Remark: [Yang Liu] The key lemma in the problem seems to come out of nowhere.

Here is how I came up with the key lemma:
$f(a,b)=1$ if and only if the length of the continued fraction (without an ending $1$ ) of $a/b$ is odd. The parity of the length leads me to consider the difference of the continued fractions. Suppose that after truncating the last term the continued fraction becomes $c/d$ , then we have
$ad-bc = (-1)^{f(a,b)-1}.$ If we instead only decrease the last term by $1$ and get $c'/d'$ , then
$ad'-bc' = (-1)^{f(a,b)}.$ It is clear that $d\leq d'<b$ , and so the lemma follows immediately.

You didn't prove b/2 is greater than d, how do you prove the lemma?

According to the property of continued fractions, we hae $ad,ad'\equiv \pm 1\mod b$ . Therefore $d+d'=b$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

635 posts

#11 h May 16, 2020, 6:49 AM

Y by

ISL 2017 N8 lemma wrote:

For any two coprime integers $a,b$
$f(x,y) = 1$ iff the inverse of $a\pmod{b},$ taken in the set $\{1, 2,..., b\},\leqslant\tfrac b2.$

Applying induction for $f(k,1)=0, f(1,k)=1$ and it's easy to verify the claim.
Claim-Any pair of relatively prime numbers can be built up from $(k,1)$ or $(1,k)$ by switching or $(a,b)\mapsto(a+b,b).$ It suffices to show that if the claim holds for $(a,b),$ then it also holds for $(b,a)$ and $(a+b,b).$
Proof 1- $(a,b)\mapsto(a+b,b)$ is easy to prove.They both have the same $f$ value, and $a$ and $a+b$ have the same inverse.
Proof 2-
$(a,b)\mapsto(b,a)$ suppose the inverse of $a\pmod{b}$ is $t.$ Then, $at-kb=1,$ for some $0\leqslant k<a$
It follows that $b(a-k)-1= a(b-t)$ is divisible by $a.$ So the inverse of $b\pmod{a}= a-k$
If $t\le\tfrac b2,$ then $at\le\frac {ab}{2}.$ Hence, $a(b-t)\ge\frac {ab}{2}\implies b(a-k)>\frac {ab}{2},$ and $a-k>\tfrac a2.$
Conversely, if $t>\tfrac b2,$ then $a(b-t)<\frac {ab}{2}\implies b(a-k)\leqslant\frac {ab}{2}$ and $a-k\le\tfrac a2$

There is a potential issue if one of $a$ and $b$ is $1$ and the other is odd. Hence, we include all of those in the base case.

Remark- This shows that if the claim holds for $(a,b).$ It also holds for $(b,a).$ B by induction, it holds for anything reachable from $(1,1)$ by $(a,b)\mapsto(a+b,b)$ or $(b,a),$ which is all pairs of relatively prime integers.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

643 posts

#12 h Jun 7, 2020, 8:37 AM • 4 Y

Y by mueller.25, Mango247, Mango247, Mango247

MarkBcc168 wrote:

Let $p$ be an odd prime number and $\mathbb{Z}_{>0}$ be the set of positive integers. Suppose that a function $f:\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}\to\{0,1\}$ satisfies the following properties:

$f(1,1)=0$ .
$f(a,b)+f(b,a)=1$ for any pair of relatively prime positive integers $(a,b)$ not both equal to 1;
$f(a+b,b)=f(a,b)$ for any pair of relatively prime positive integers $(a,b)$ .

Prove that
$\sum_{n=1}^{p-1}f(n^2,p) \geqslant \sqrt{2p}-2.$

Solution. Clearly, $f(a,b)=1$ if and only if the pair $(a,b)$ can be obtained from $(1,2)$ by composing the two operations $(a,b)\mapsto (a+b,b)$ and $(a,b)\mapsto (a,a+b)$ in some manner, in other words, this is the reverse of Euclidean Algorithm. Consider all the pairs $(a,b)$ as vectors $\begin{bmatrix}a \\ b\end{bmatrix}$ and define
$A=\begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix}\text{ and } B=\begin{bmatrix}1 & 0 \\ 1 & 1\end{bmatrix}.$ The pairs $(x,y)$ which can be generated from $(1,2)$ using the two discussed operations will satisfy
$M\begin{bmatrix}1\\ 2\end{bmatrix}=\begin{bmatrix}x \\ y\end{bmatrix}$ where $M$ is a matrix which can be expressed as a sequence of compositions of $A$ and $B.$

Claim. A $2\times 2$ matrix $M$ can be expressed as a sequence of compositions of $A$ and $B$ if and only if $\det M=1$ and all its entries are non-negative integers.

Proof. It is clear that a matrix which can be written as compositions of $A$ and $B$ must have all its entries non-negative integers and its determinant must be $1$ since $\det A=\det B=1.$ To prove the other part let us induct on the sum of the entries of the matrix $M.$ Let $M=\begin{bmatrix}a & b \\ d & c\end{bmatrix},$ we have $ac-bd=1,$ notice that $A^{-1}=\begin{bmatrix} 1 & -1 \\ 0 & 1\end{bmatrix}$ and $B^{-1}=\begin{bmatrix} 1 & 0 \\ -1 & 1\end{bmatrix},$ therefore
$\begin{align*} MA^{-1}=\begin{bmatrix}a & b \\ d & c\end{bmatrix}\begin{bmatrix} 1 & -1 \\ 0 & 1\end{bmatrix}=\begin{bmatrix}a & b-a \\ d & c-d\end{bmatrix}\\ MB^{-1}=\begin{bmatrix}a & b \\ d & c\end{bmatrix}\begin{bmatrix} 1 & 0 \\ -1 & 1\end{bmatrix}=\begin{bmatrix}a-b & b \\ d-c & c\end{bmatrix} \end{align*}$ If any of $MA^{-1}$ and $MB^{-1}$ has all entries non-negative then we are done by induction hypothesis as sum of entries of both $MA^{-1}$ and $MB^{-1}$ are less than that of $M.$ Let's assume the contrary that in both of $MA^{-1}$ and $MB^{-1}$ there is a negative entry. Clearly $b\ge a,~c\le d$ is not possible as $ac-bd=1$ so $a\ge b,~c\ge d,$ observe that at least one of the two inequalities must be strict, so without loss of generality assume $a>b\implies a\ge b+1$ then we obtain $bd+1=ac\ge d(b+1)\implies d\in\{0,1\},$ if $d=0$ then clearly this forces $M=I$ where $I$ is the identity matrix but $I=A^0$ so this case is okay, else if $d=1$ then $c=d=1$ and $a=b+1,$ but observe that in this case $MB^{-1}$ has non-negative entries so again we are done by induction hypothesis. Our induction is complete, hence the claim. $~\square$

By the above claim, it follows that $f(m,n)=1$ if and only if there exist a matrix $T=\begin{bmatrix}a & b \\ d & c\end{bmatrix}$ whose all entries are non-negative integers and $\det T=1$ with $T\begin{bmatrix}1\\ 2\end{bmatrix}=\begin{bmatrix}m \\ n\end{bmatrix}\iff m=a+2b\text{ and }n=d+2c,$ notice that $mc-nb=ac-bd=\det T=1,$ now it is not hard to see that $f(m,n)=1$ if and only if the inverse of $m$ reduced modulo $n$ is less than or equal to $\tfrac n2.$ Since there are at least $\sqrt{\tfrac p2}-1$ perfect squares in $[1,\tfrac{p-1}2]$ hence the desired bound is obvious. $~\blacksquare$

This post has been edited 4 times. Last edited by ayan.nmath, Jun 7, 2020, 9:07 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

779 posts

#13 h Jul 23, 2020, 5:52 PM

Y by

For a prime $p,$ let $Q_p$ denote the set of quadratic residues modulo $p.$

Additionally, for relatively prime positive integers $a,b,$ let $D(a,b)$ denote the number of times the Euclidean Algorithm must be applied to $(a,b)$ to reach $(c,1)$ or $(1,c)$ for some $c.$

$\textbf{Claim: }$ For all integers $x>1,$ we have $f(1,x)=-f(x,1)=1.$ $\textbf{Proof: }$ Note that $f(a,1)=f(a+1,1)$ for all integers $a>1,$ so the claim is obvious by induction. $\blacksquare$

$\textbf{Claim: }$ For an integer $a>1$ and an odd prime $p,$ we have $f(a,p)=1\iff D(a,p)\equiv 0\pmod{2}$ $\textbf{Proof: }$ Observe that the given functional equation preserves the value of $f(a,b)$ as we apply the Euclidean Algorithm to $(a,b).$ Furthermore, notice that $\min(a,b)$ decreases at each application of the algorithm.

Therefore, if $D(a,b)$ is even, then $f(a,b)=f(1,c)=1,$ and if $D(a,b)$ is odd, then $f(a,b)=f(c,1)=0.$ $\blacksquare$

$\textbf{Claim: }$ For an integer $a>1$ and an odd prime $p,$ we have $D(a,p)\equiv 0\pmod{2}\iff a^{-1}\in\{1,2,\dots,(p-1)/2\}\pmod{p}.$ $\textbf{Sketch: }$ We can use the Euclidean Algorithm to determine a solution to the equation $ma+np=1$ with $|m|,|n|\le (p-1)/2.$ The signs of $m,n$ depend on the parity of $D(a,b).$ $\blacksquare$

Thus, for all positive integers $a$ a odd primes $p,$ $f(a,p)=1\iff a^{-1}\in\{1,2,\dots,(p-1)/2\}\pmod{p}.$ Note that $a\in Q_p$ if and only if $a^{-1}\in Q_p.$ Therefore, $\sum_{n=1}^{p-1}f(n^2,p)=2\sum_{m\in Q_p}f(m,p)=2\#(Q_p\cap\{1,2,\dots,(p-1)/2\}).$ But since the squares of $1,2,\dots,\lfloor\sqrt{(p-1)/2}\rfloor$ are distinct integers in the set $\{1,2,\dots,(p-1)/2\},$ we know $\#(Q_p\cap\{1,2,\dots,(p-1)/2\}\ge\lfloor\sqrt{(p-1)/2}\rfloor.$ Hence $\begin{align*}\sum_{n=1}^{p-1}f(n^2,p) &=2\#(Q_p\cap\{1,2,\dots,(p-1)/2\})\\ &\ge 2\lfloor\sqrt{(p-1)/2}\rfloor \\ &\ge\sqrt{2p}-2,\end{align*}$ as desired.

This post has been edited 1 time. Last edited by amuthup, Jul 23, 2020, 5:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

830 posts

niyu

#14 h Dec 29, 2020, 5:04 AM

Y by

Characterization of $f$ : For relatively prime $(a, b)$ , we have $f(a, b) = 1$ iff $a^{-1} \pmod{b} \leq \frac{b}{2}$ (where $a^{-1} \pmod{b}$ is taken to denote the smallest positive integer inverse).

Proof: Strong induct on $b$ , with base case $b = 1$ obvious (we have $f(a, 1) = 0$ for all $a$ ). For the inductive step, suppose for $a < b$ that $f(a, b) = 1$ . Since $f(b, a) = 0$ , by hypothesis it follows that $b^{-1} \pmod{a} \geq \frac{a}{2}$ . Letting $b'$ denote this inverse, we have for some integer $k$ that $bb' = ak + 1$ . Note that $ak \equiv -1 \pmod{b}$ , so $b - k$ is an inverse of $a$ modulo $b$ . Yet we also have $ak + 1 \geq \frac{ab}{2}$ , so $k \geq \frac{b}{2}$ . As such, $b - k \leq \frac{b}{2}$ , completing this direction of the induction. The converse follows identically. $\blacksquare$

We now solve the given problem. Let $S$ denote the set of quadratic residues modulo $p$ , and note that $s \in S$ iff $s^{-1} \in S$ (inverses taken mod $p$ ). Note also that $f(n^2, p) = 1$ iff $n^{-2} \pmod{p} < \frac{p}{2}$ . We have
$\begin{align*} \sum_{n = 1}^{p - 1} f(n^2, p) = 2\sum_{s \in S} f(s, p) = 2\sum_{s \in S, s^{-1} < \frac{p}{2}} 1 = 2\sum_{s \in S, s < \frac{p}{2}} 1 \end{align*}$ where the third step follows from the above claim. However, there are $\sqrt{\frac{p}{2}} - 1$ distinct positive integer solutions to $k^2 < p$ , implying that there are at least that many elements of $S$ which are less than $\frac{p}{2}$ . Thus, the above sum is at least $2\left(\sqrt{\frac{p}{2}} - 1\right) = \sqrt{2p} - 2$ , as desired. $\Box$

This post has been edited 1 time. Last edited by niyu, Dec 29, 2020, 5:05 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeronimoStilton

1521 posts

GeronimoStilton

#15 h Feb 22, 2021, 4:29 PM • 1 Y

Y by Mango247

Solution with awang11.

Note that
$f(a,a+b)=1-f(a+b,a)=1-f(b,a)=f(a,b)$ and $f(1,2)=1$ , so $f(1,k)=1$ for all $k>1$ by an easy induction.

We claim that for $b>1$ , $f(a,b)$ is $1$ iff the residue $r$ of $a^{-1}$ modulo $b$ is at most $b/2$ , with equality only holding at $b=2$ . The proof is by strong induction on $a+b$ with the base case being $a=1$ and $b=2$ , which are both trivial.

If $a>b$ , the result is immediate. If $a<b$ , we are either done because $a=1$ , or we have $a\ge 2$ . In the latter case, let $r$ denote the residue of $a^{-1}$ modulo $b$ . For some $k$ , we have $ar-1=kb$ , so $(a-k)b-1=ab-kb-1=ab-ar=a(b-r)$ . Then $r<b/2$ iff $(a-k)b>ab/2$ implying $a-k>b/2$ , so we are done.

Then, the sum is counting all $n$ for which the residue of $n^{-2}$ modulo $p$ is at most $p/2$ . But this is equivalent to counting all $n$ for which the residue of $n^2$ modulo $p$ is at most $p/2$ . We can explicitly count $2\lfloor \sqrt{p/2}\rfloor$ such residues:
$n=1,2,3,\dots,\lfloor \sqrt{p/2}\rfloor, p-\lfloor \sqrt{p/2}\rfloor, \dots, p-3,p-2,p-1.$ As $p\ge 2\lfloor \sqrt{p/2}\rfloor$ because $p^2\ge 2p$ , we are done.

This post has been edited 1 time. Last edited by GeronimoStilton, Feb 22, 2021, 4:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1184 posts

L567

#16 h Jul 4, 2021, 4:44 AM • 1 Y

Y by starchan

Solved with Pujnk

We claim $f$ is defined as follows. Define it arbitrarily for non coprime numbers. And for two coprime numbers $x,y$ , we have $f(x,y) = 1$ if and only if $\frac{1}{x} \pmod y \le \frac{y}{2}$

Obviously, the given conditions say nothing about non coprime numbers since $\gcd(a+b,b) = \gcd(a,b)$ . So, we can define $f$ arbitrarily for those. For the rest, induct on the value of $y$ . Its easy to see that $f(n,1) = 0$ and $f(1,n) = 1$ for all $n > 1$

Now, suppose we have shown that the claim holds for $f(x,y')$ with $y' < y-1$ and now we need to find $f(x,y)$ with $x < y$ . We have $f(x,y) = 1- f(y,x)$ and since $x < y$ , we know the value of $f(y,x)$ . So, to show the statement is true, we must show that the inverse of $x$ mod $y$ is $\le \frac{y}{2}$ if and only if the inverse of $y$ mod $x$ is $> \frac{y}{2}$

Let $a$ be the inverse of $x$ and let $b$ be the inverse of $y$ . Obviously, $a < y$ and $b < x$

We have $y | ax - 1$ and $x | yb-1$ . Let $ky = ax - 1$ and $lx = yb-1$

So, we have $ax-ky = 1 = by-lx \implies (a+l)x = (b+k)y$ . Since $x,y$ are coprime, this means $y | a+l$ . Suppose $a + l > y \implies a+l \ge 2y \implies l > y$ . But then $y < l = \frac{yb-1}{x} < \frac{yb}{x} \implies b > x$ , a contradiction.

This means $a+l = y$ and similarly, $b+k = x$ . So, the equation we had is now $ax + by - xy = 1$

Suppose both $a > \frac{y}{2}$ and $b > \frac{x}{2}$ (The case when both are $<$ is also similar) and let $p = a - \frac{y}{2}$ and $q = b - \frac{x}{2}$

Then, we must have $px + qy = 1$ , which is impossible unless $x=y=p=q=1$ , but since we already did that base case, this is impossible. So, the claim holds.

Now, to finish, consider the numbers in the range $\{1,2,...,\sqrt{\frac{p}{2}}\}$ . This has $\lfloor \sqrt{\frac{p}{2}} \rfloor \ge \sqrt{\frac{p}{2}} - 1$ numbers. For each number $k$ in it, we have $f \left(\frac{1}{n^2}, p \right) = 1$ as well as $f \left(\frac{1}{(-n)^2}, p \right) = 1$ because their inverses are in this range and so $\le \frac{p}{2}$

So, we have at least $2 \left(\sqrt{\frac{p}{2}} - 1 \right) = \sqrt{2p}-2$ ones, and so we have $\sum_{n=1}^{p-1}f(n^2,p) \geqslant \sqrt{2p}-2$ , as desired. $\blacksquare$

This post has been edited 1 time. Last edited by L567, Jul 4, 2021, 4:44 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1455 posts

#17 h Mar 31, 2022, 5:35 PM • 1 Y

Y by gvole

Joke of a question.

Clearly, $f$ describes the parity of the height of the continued fraction of $\frac{a}{b}$ . Since the fraction is rational, any true connoisseur of continued fractions will know that the function is equal to one if and only if the Beatty sequence of the fraction hits 1 mod p before -1 mod p, in other words, the final boundary extension is on the left. This is equivalent to saying the square of the inverse of n is less than $\frac{p-1}{2}$ (occurs before the negative square of the inverse), so since inverting just permutes the complete residue set, now it is equivalent to proving the number of quadratic residues mod p that are less than $\frac{p}{2}$ is at least equal to half the bound (since squaring ignores sign). Trivially, we have at least $\left \lfloor \sqrt{\frac{p}{2}} \right \rfloor$ solutions less than half of p, so adding in their negatives gives the desired bound of $\sqrt{2p}-2$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

966 posts

#18 h Aug 8, 2022, 1:45 AM • 1 Y

Y by rama1728

Solved with rama1728.

Claim: For coprime $a,b$ we have $f(a,b) = 1$ iff the integer $x \equiv a^{-1}\pmod{b}$ in set $\{1,2, \cdots , b \}$ is $\le\frac{b}{2}.$

The function satisfies the first and third conditions. For the second, define integer $y \equiv b^{-1}\pmod{a}$ in set $\{1,2, \cdots , a \}.$ Note $xa + yb \equiv 1 \pmod{ab}$ but is $>1$ and $<2ab+1$ by size, so $xa+yb = ab+1.$ So $x \le \frac{b}{2} \iff xa \le \frac{ab}{2} \iff yb > \frac{ab}{2} \iff y > \frac{a}{2}$ and vice versa (since $ab+1 > 2$ ). $\square$

To finish, note that $n \in \left [1, \left \lfloor \sqrt{p/2} \right \rfloor \right ] \cup \left[p-\left \lfloor \sqrt{p/2} \right \rfloor, p-1 \right ]$ yield $f(n^2,p) = 1.$ $\blacksquare$

This post has been edited 2 times. Last edited by squareman, Aug 8, 2022, 1:50 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

800 posts

#19 h Aug 8, 2022, 2:29 PM • 1 Y

Y by megarnie

squareman wrote:

Solved with rama1728.

Claim: For coprime $a,b$ we have $f(a,b) = 1$ iff the integer $x \equiv a^{-1}\pmod{b}$ in set $\{1,2, \cdots , b \}$ is $\le\frac{b}{2}.$

The function satisfies the first and third conditions. For the second, define integer $y \equiv b^{-1}\pmod{a}$ in set $\{1,2, \cdots , a \}.$ Note $xa + yb \equiv 1 \pmod{ab}$ but is $>1$ and $<2ab+1$ by size, so $xa+yb = ab+1.$ So $x \le \frac{b}{2} \iff xa \le \frac{ab}{2} \iff yb > \frac{ab}{2} \iff y > \frac{a}{2}$ and vice versa (since $ab+1 > 2$ ). $\square$

To finish, note that $n \in \left [1, \left \lfloor \sqrt{p/2} \right \rfloor \right ] \cup \left[p-\left \lfloor \sqrt{p/2} \right \rfloor, p-1 \right ]$ yield $f(n^2,p) = 1.$ $\blacksquare$

I would like to add some remarks on this groupsolve. Though this solution looks pretty unmotivated, there is a huge motivation behind all these (I'll also share about some of the back-story)

Backstory

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

107 posts

#20 h May 20, 2023, 12:14 PM

Y by

If you are quite familiar with Bezout, the problem may not seen to be too difficult. But the problem is really a nice one for TST!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

577 posts

#21 h Sep 5, 2023, 6:48 AM

Y by

Claim: [characterization] We have $f(a, b) = \begin{cases} 1 & (a^{-1} \bmod{b}) \le b/2 \\ 0 & (a^{-1} \bmod{b}) > b/2. \end{cases}$
Proof. Consider the matrices $A=\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ and $B=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ . Construct the matrix $M_{a, b}$ as follows.

Begin with the vector $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ .
Now perform the following process: following the Euclidean algorithm, apply $A$ and $B$ repeatedly until you reach $\begin{bmatrix} a \\ b \end{bmatrix}$ .
In each step, choose the matrix so that the $x$ -component is always at least the $y$ -component.
Finally, $M_{a, b}$ is the matrix given by the product of the matrices used in the above process.

Note that $\det A = +1$ and $\det B = -1$ , so $\det M_{a, b} \in \{+1, -1\}$ . By induction, it's easy to observe that if $M_{a, b} = \begin{bmatrix} a & x \\ b & y \end{bmatrix}$ then $a \ge 2x$ and $b \ge 2y$ . In the context of $M_{a, b}$ , we may redefine $f(a, b)$ as $f(a, b) := \begin{cases} 1 & \det M_{a, b} = 1 \\ 0 & \det M_{a, b} = -1, \end{cases}$ so it remains to do casework on $\det M_{a, b} = ay-bx$ . If $ay-bx=1$ , then $y \equiv a^{-1} \pmod{b}$ , so by the $b \ge 2y$ bound, $\det M_{a, b} = 1$ iff $(a^{-1} \bmod{b}) \le b/2$ . Therefore, the desired characterization of $f$ holds.
:yoda:

:yoda:

The rest is just technical work. Let $S$ be the set of inverses of the numbers in $\{\pm 1, \pm 2, \ldots, \pm \lfloor \sqrt{p/2} \rfloor\}$ , and by the claim $\sum_{n=1}^{p-1}f(n^2,p) = \sum_{n=1}^{p-1}f(n^{-2} \bmod{p},p) \ge \sum_{i \in S} f(i^2, p) = 2\lfloor\sqrt{p/2}\rfloor \le \sqrt{2p}-2,$ finishing.

This post has been edited 2 times. Last edited by Leo.Euler, Sep 7, 2023, 1:38 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

53 posts

mcmp

#22 h Mar 31, 2025, 1:46 AM • 1 Y

Y by ohiorizzler1434

This question is pure insanity. Solved with ohiorizzler1434 with a lot of gruntwork.

We split the proof into two parts. The first is characterising $f$ , which seems well-nigh impossible but somehow has an almost beautiful characterisation, and the second part is a trivial bound on the sum.

Part 1: Characterising
I claim that:
$\begin{align*} f(a,b)=\begin{cases}1&(a^{-1}\bmod{b})\le\frac{b}{2}\\0&(a^{-1}\bmod{b})>\frac{b}{2}\end{cases} \end{align*}$ This however is pretty chill. Notice that $f(1,1)=0$ is satisfied by both functions, and further $f(a+b,b)=f(a,b)$ is easy to see as $(a+b)^{-1}\equiv a^{-1}\pmod{b}$ , so we only need to check the second condition. However let $x=a^{1}\bmod{b}$ . Then:
$\begin{align*} ax-by&=1 \end{align*}$ for some $y\in\mathbb{Z}_{>0}$ . If $x>\frac{b}{2}$ then it is clear that $y>\frac{a}{2}$ , and furthermore $y\equiv -b^{-1}\pmod{a}$ , so $b^{-1}\pmod{a}<\frac{a}{2}$ . The other direction obviously holds by symmetry. So $f$ matches with its purported characterisation and thus we are done.

Part 2: Finishing
Notice that $\{n^{-2}\bmod{p}\}_{n=1}^{p-1}=\{n^2\bmod{p}\}_{n=1}^{p-1}$ , so as $f(n^{-2},p)=1$ iff $n^2\bmod{p}\le\frac{b}{2}$ , we only need to find the number of such elements, and then multiply by two. But then clearly if we take $x=1,2,\dots,\sqrt{\frac{p-1}{2}}$ , we actually instantly get at least $\sqrt{\frac{p-1}{2}}$ such elements. Multiplying by $2$ we get at least $\sqrt{2(p-1)}>\sqrt{2p}-2$ elements that work. (The inequality holds as it rearranges to $p>\frac{3}{\sqrt{2}}$ , which clearly holds). This completes the proof of this devilish problem.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a