Dynamical Number Theory

Number Theory Level 4

Consider the following function $f: \{0,\dots,52\} \rightarrow \{0,\dots,52\}$

$f(x)=x^2+2x+3 \text{ (mod 53)}$

How many integers $0 \leq x \leq 52$ exist such that $f^n(x) \equiv 18 \text{ (mod 53)}$ , for some positive integer $n$ ?

Note that $f^1(x)=f(x)$ , $f^2(x)=f(f(x))$ and $f^n(x)$ is function $f(x)$ , composed by itself $n$ times.

The answer is 14.

1 solution

Henry U
Oct 26, 2018

We can make a list of all function values $(n, f(n)$ and then work our way backwards.

First, we look for $f^1(n) = 18$ . These are just all values $n$ for which $f(n)$ gives 18. If we look at our list, $3$ and $48$ are the only numbers satisfying this.

Then, we search values so that $f(n)=3 \lor f(n)=48$ . For this, we find $0$ , $23$ , $28$ , $51$ .

We proceed like this, now looking for $n$ s that give $0$ , ( 23 ), $28$ or ( 51 ) and find $6$ and $45$ , then $1$ , $18$ , ( 33 ) and $50$ , next $3$ , but we've counted it already, $22$ , $29$ and $48$ which we've also already counted. After that, there aren't any more numbers.

So we have found $\{ 3, 48, 0, 23, 28, 51, 6, 45, 1, 18, 33, 50, 22, 29 \}$ , or (sorted) $\{ 0, 1, 3, 6, 18, 22, 23, 28, 29, 33, 45, 48, 50, 51 \}$ , which is a total of 14 numbers.

Good on you!

A Former Brilliant Member - 2 years, 7 months ago

Is there a reason why you chose mod 53 and 18? They seem so arbitrary, but maybe it has something to do with the fact that the solutions come in pairs whose sum is always 51 ( $0+51=1+50=3+48=6+45=\ldots$ ).

Henry U - 2 years, 7 months ago

Actually, all function values come in pairs with sum 51.

$a+b=51 \Rightarrow f(a)=f(b)$ .

Do you know if this is always the case for quadratic functions modulo n?

Henry U - 2 years, 7 months ago

@Henry U – I'm thinking off the top of my head, but I think, for a quadratic ax^2+bx+c (mod p) and 0<a,b<p, numbers come in such pairs (t,k) when (p-b) is divisible by a. If a=1, then they definitely pair up.

A Former Brilliant Member - 2 years, 7 months ago

@A Former Brilliant Member –

$(51-n)^2+2(51-n)+3 = n^2-104n+2706$

$\equiv (n^2 \pmod {53}) + (-104n \pmod {53}) + (2706 \pmod {53}) \equiv n^2+2n+3 \pmod {53}$

and for some prime $p$

$((p-2)-n)^2+2((p-2)-n)+3 = n^2-2pn+2n+p^2-2p+3$

$\equiv (n^2 \pmod p) + (-2pn+2n \pmod p) + (p^2-2p+3 \pmod p) \equiv (n^2 \pmod p) + (2n \pmod p) + (3 \pmod p)$

So it actually works with this polynomial and any prime $p$ .

I've written a note about that , I will write more thoughts over there.

Henry U - 2 years, 7 months ago

@Henry U – nice, kid! you are more active than me, when im on cocaine :D

A Former Brilliant Member - 2 years, 7 months ago

I took a small random prime and a random quadratic poly. then I just started playing with them. I did not know where it was going. You know, I had Friday night sadness... :D the reason for 18 is that it was part of a dynamical loop in the given dynamics. In other words, it was not a transient state in the dynamics, so you do not need to worry how many times you compose functions to get to 18, starting from a state in the corresponding diagram in which the loop is.

A Former Brilliant Member - 2 years, 7 months ago

Dynamical Number Theory

The answer is 14.

1 solution

0 pending reports