Testing 10 digit numbers

the only such $n$ are the Fermat primes. To prove this, first add 1 to both sides of the recursion to get $x_{i+1,m}+1=x_{i,m}^2+2x_{i,m}+1=(x_{i,m}+1)^2$ Use this equation $n$ times to get the general formula $x_{n,m}+1=(x_{0,m}+1)^{2^n}=(m+1)^{2^n}$ Let $l=m+1$ , then the condition reduces to for all $2\leq l\leq n-1$ , $l^{2^n}\equiv 1\mod n$ .

Let $p$ be a prime divisor of $n$ , and let $l=n/p$ .If $l>1$ , then since it is a divisor of $n$ , $(l,n)>1$ , so $(l^{2^n},n)>1$ . However, this contradicts the condition that $l^{2^n}\equiv 1\mod n$ . Hence, $l=1$ , and $n$ is a prime.

By a classical theorem in number theory, $n$ has a primitive root $g$ , i.e. the order of $g$ mod $n$ is $n-1$ . Since $2^n>n-1$ , and $g^{2^n}\equiv 1\mod n$ , we must have $n-1|2^n$ . Therefore, $n=2^r+1$ for some integer $r$ . If $r$ has an odd factor, the expression factors, so $n$ is not a prime. Therefore, $r$ is also a power of 2, so $n$ is a prime of the form $2^{2^k}+1$

This is a prime if $k=0,1,2,3,4$ . When $k=5$ , it is divisible by 641, and if $k$ is higher, $n$ is greater than $10^{10}$ . Therefore, $N=3+5+17+257+65537=65819$

Let us define another series $y_{n,m} = x_{n,m}+1$ , so we get $y_{0,m} = m+1$ and $y_{i+1,m} =$ $x_{i+1,m}+1 = x_{i,m}^2 + 2x_{i,m} + 1$ $= (x_{i,m}+1)^2$ $= y_{i,m} ^2$ . From this we can directly get $y_{n,m} = y_{0,m} ^{2^n}$ and thus $x_{n,m} +1 = (m+1) ^{2^n} \Rightarrow x_{n,m} = (m+1)^{2^n} - 1$

Now, it is given that $n \mid x_{n,m} \Rightarrow n \mid (m+1)^{2^n} - 1 \forall 1 \le m \le n-2$ , or it can be stated as $n \mid i^{2^n} - 1 \forall 2 \le i \le n-1$ Now, let's assume $n$ is not a prime. Then let $d \le n-1$ be a divisor of $n$ . From $n \mid d^{2^n} - 1$ we get that $d^{2^n} - 1 = nk = dk'$ for some integer $k' > 1$ , but then $k' \mid 1$ , a contradiction. So $n$ is a prime.

As $n$ is a prime, there exists a primitive root modulo $n$ . Let it be $x$ .We get from $n \mid i^{2^n} - 1 \forall 2 \le i \le n-1$ that $n \mid x^{2^n} - 1$ , and from Fermat's last theorem, $n \mid x^{n-1} - 1$ . As $x$ is a primitive root, we get that $n-1 \mid 2^n$ . So, $n-1 =2^t$ for some $t$ , or $n$ is a prime of the form $2^t+1$ .

Now if $t$ had a odd divisor, let it be $a$ . Then $2^a+1 \mid (2^a)^{t/a} +1=$ $2^t+1 \Rightarrow$ $2^a+1 \mid n$ , which is a contradiction as $n$ is a prime. So, $t$ has no odd divisor, which implies $t = 2^x$ for some $x$ , and thus $n$ is a prime of the form $2^{2^x} +1$ , which means $n$ is a Fermat prime.

Now the only known Fermat prime (and only the ones less than or equal $10^{10}$ ) are $3,5,17,257,65537$ . So $n$ can be only $3,5,17,257,65537$ , and thus $N = 3+5+17+257+65537 =65819$ , and thus the last 3 digits of $N$ is $819$ , and thus our answer is $819$ .

Throughout this solution, let's use the notation $a \equiv_n b$ to denote the congruence $a \equiv b$ (mod $n$ ).

First, let's figure out exactly what the recurrence relation tells us. Completing the square gives us

$x_{i+1,m} = x_{i,m}^2 + 2x_{i,m} = (x_{i,m}+1)^2-1 \; \; \; \; \;$ for $i = 0,1,2,\ldots$

So for any $m$ , a term in the sequence is computed by taking the previous term, adding 1, squaring, then subtracting 1. We find that the first few terms of the sequence will look like

$\{m,(m+1)^2-1,(m+1)^4-1,(m+1)^8-1,\ldots\}$ .

We've discovered that $x_{n,m} = (m+1)^{2^n}-1$ for all $n$ and $m$ . Using the change of variables $k=m+1$ for ease of notation, we are thus tasked with finding all integers $3 \leq n \leq 10^{10}$ such that $n \mid (k^{2^n}-1)$ for all $2 \leq k \leq n-1$ . Equivalently, we require

$k^{2^n} \equiv_n 1$ for all $2 \leq k \leq n-1$ .

We can narrow down the cases quickly. If $n$ is composite, say $n=pq$ with $p$ prime and $q > 1$ , then we necessarily require $k^{2^n} \equiv_p 1$ . However, this fails for $k=p$ , which is certainly between 2 and $n-1$ . Thus $n$ must be prime.

Let $n = p$ be a prime number such that $p-1 \nmid 2^p$ , so $2^p = q(p-1)+r$ for some $q \in \mathbb{Z}$ and remainder $1 \leq r \leq p-2$ . We thus require that $k^{q(p-1)}k^r \equiv_p 1$ for all $2 \leq k \leq p-1$ . By Fermat's Little Theorem , since $k^q$ is not divisible by $p$ (since $2 \leq k \leq p-1$ ), we know that $k^{q(p-1)} \equiv_p 1$ . Thus our required condition becomes

$k^r \equiv_p 1$ for all $2 \leq k \leq p-1$ , where $1 \leq r \leq p-2$ is fixed.

However, this condition implies that $r \geq \lambda(p)$ , where $\lambda$ is the Carmichael function . Carmichael's theorem gives us that since $p$ is prime, $\lambda(p) = p-1$ , contradicting the assumption that $1 \leq r \leq p-2$ . Thus, $n$ must be a prime $p$ such that $p-1 \mid 2^p$ . By setting $r = 0$ in the recent argument, we see immediately that any such prime satisfies the desired condition!

Thus we seek all primes $3 \leq p \leq 10^{10}$ such that $p-1 \mid 2^p$ . To look for them, we note that such primes must satisfy $p-1 = 2^q$ for some $q$ . Equivalently, they must satisfy

$p = 2^q +1$ for some $q$ .

I claim that, since $p \geq 3$ is prime (so $q \geq 1$ ), such $q$ must be a power of 2. Suppose that $q$ has some odd factor $r > 1$ , so $q = rs$ , with $s \geq 1$ . Then

$p = 2^q+1 = (2^s)^r + 1 \equiv_{2^s+1} (-1)^r + 1 = 0$ ,

implying $2^s+1 \mid p$ , a contradiction since $s < q$ implies $2^s+1 < p$ .

Thus we conclude that we seek all primes $3 \leq p \leq 10^{10}$ such that $p = 2^{2^n}+1$ for some $n$ . Fortunately, we can recognize these numbers: they are known as the Fermat numbers , $F_n = 2^{2^n}+1$ . Fermat had once falsely conjectured that all Fermat numbers are prime ( $F_5$ is composite, for example), but it is known that $F_0, F_1,F_2,F_3,$ and $F_4$ are prime! As mentioned, $F_5$ is composite (so we don't want it), and $F_6 > 10^{10}$ , so we finally arrive at our desired set of numbers: $F_0=3$ , $F_1=5$ , $F_2=17$ , $F_3=257$ , $F_4=65537$ .

Adding these numbers up gives $N = 65819$ , from which we obtain the final three digits 819 .

Note that $x_{0,m}+1 = m+1$ and $x_{i+1,m}+1 = (x_{i,m}+1)^2$ . By induction, it can be shown that $x_{n,m}+1 = (m+1)^{2^n}$ , and so, $x_{n,m} = (m+1)^{2^n}-1$ .

If $n$ is not prime, then pick an $m = p-1$ where $p \mid n$ is prime. Then, $x_{n,m} = p^{2^n}-1 \equiv -1 \pmod{p}$ . So, $p \nmid x_{n,m}$ , and thus, $n \nmid x_{n,m}$ , a contradiction. Therefore, $n$ must be prime.

If $x_{n,m} \equiv 0 \pmod{n}$ , i.e. $(m+1)^{2^n} \equiv 1 \pmod{n}$ for all $1 \le m \le n+2$ with $n$ prime, then we need $n-1 \mid 2^n$ . Hence, $n-1 = 2^r$ , i.e. $n = 2^r+1$ for some integer $r$ .

It is well-known that if $n = 2^r+1$ is prime, then $r$ must be a power of $2$ , i.e. $r = 2^k$ and $n = 2^{2^k}+1$ for some non-negative integer $k$ .

If $k \ge 6$ then $n = 2^{2^k}+1 > 10^{10}$ . Thus, we only need to check $k \le 5$ . For $k = 0,1,2,3,4,5$ we have $n = 3, 5, 17, 257, 65537, 4294967297$ , of which, the first five are prime, while $4294967297$ is divisible by $641$ .

Therefore, $N = 3+5+17+257+65537 = 65819 \equiv \boxed{819} \pmod{1000}$ .

[We will ignore the subscript $m$ .]

First, denote $x_i+1$ by $y_i$ for all $i$ . Then $x_{i+1}=x_i^2+x_i$ is equivalent to $y_{i+1}=y_i^2.$ So $y_i=m^{2^i},$ and $x_n = m^{2^n} -1$ . If $n$ is not prime, then take take $m | n, m \neq 1$ , we can see that $m \not \mid x_n$ , hence $m \not \mid x_n$ . Thus, we must have $n$ prime, which we will denote as $p$ for convenience.

Now note that $1\leq x_0\leq p-2$ condition is equivalent to $2\leq y \leq p-1$ and $p|x_p$ is equivalent to $y_p\equiv 1 \pmod p .$

We will now prove two lemmas.

Lemma 1. Suppose $p$ is a prime number. Then $m^{2^p}\equiv 1$ for all $m=1,2,...,p-1$ if and only if $p-1$ is a power of $2$ .

In one direction, if $p-1=2^k,$ then clearly $k\leq p$ . By the Fermat's theorem, for any $m \not \equiv 0 \pmod p,$ $m^{2^k}\equiv 1 \pmod p,$ so $m^{2^p}\equiv 1^{2^{p-k}}\equiv 1 \pmod p.$

In the other direction, we will give two proofs.

Proof #1. Suppose $p-1=2^k\cdot n,$ where $n>1$ is odd. Because the multiplicative group of non-zero residues modulo prime $p$ is cyclic, there exists a residue $m \not \equiv 1\pmod p,$ such that $m^n\equiv 1 \pmod p.$ Because $2^p$ and $n$ are coprime, there exists integer $u$ and $v,$ such that $u2^p+vn=1.$ Then $m\equiv m^{u2^p+vn}\equiv 1^{u}\cdot 1^v \equiv 1 \pmod p,$ a contradiction.

Proof #2. Suppose $p-1=2^k\cdot n,$ where $n>1$ is odd. Consider the polynomial with coefficients in the field of residues modulo $p$ : $P(x)=x^{2^k}-1.$ It can have no more than $2^k$ roots, and $2^k<p-1.$ So there exists $m\not \equiv 0$ such that $m^{2^k}\not \equiv 1 \pmod p.$ For such $m,$ by the Fermat's theorem, $m^{2^k\cdot n}\equiv 1 \pmod p.$ If $m^{2^p}\equiv 1 \pmod p,$ then, because $g.c.d.(2^k\cdot n,2^p)$ divides $2^k,$ there exist integers $u$ and $v,$ such that $u(2^kn)+v2^p=2^k.$ Therefore, $m^{2^k}\equiv 1^u\cdot 1^v \equiv 1 \pmod p,$ a contradiction.

Lemma 2. If $p=2^k+1$ is prime, then either $p=2$ or $p=2^{2^j}+1$ for some integer $j\geq 0.$

Proof. If $p>2,$ then $k\geq 1.$ If some odd number $q$ divides $k,$ that is $k=qr,$ then $2^k+1=(2^r+1)(2^{r(q-1)}-2^{r(q-2)}+...+1,)$ so $p$ is not prime.

With the above two lemmas, it is enough to find the prime numbers of the form $p=2^{2^j}+1,$ for $p<10^{10}.$ This means $0\leq j \leq 5.$ For $0\leq j\leq 4$ these numbers are indeed prime: $3,\ 5,\ 17,\ 257, \ 65537.$ For $j=5$ , however, $2^{2^5}+1$ is divisible by $641.$ So the sum is $3+5+17+257+65537=65819$ and the answer is $819.$

As you can see, not all numbers of the form $2^{2^j}+1$ (called Fermat numbers) are prime. In fact, they are known to be prime for $0\leq j \leq 4$ and composite for $5\leq j\leq 11$ . Not much is known beyond that, and while some heuristic arguments suggest that there are infinitely many Fermat primes, other arguments suggest that $2^{2^4}+1$ may be the last one.