Diary 2026 08 30

Learning some new techs from Richard’s online courses.

Given that,

$$ p | (n^2+1) $$

We have,

$$ n^2 \equiv -1 \pmod p \\ n^4 \equiv 1 \pmod p $$

So $4|p-1$ or $p=2$ (in which case $-1 = 1$)

Given that,

$$ p | (a^q-1), p \not\mid (a-1) $$

where $p,q$ are primes. We learn that,

$$ a^q \equiv 1\pmod p $$

So the order of $a$ could only be $q$ or $1$. We also know from $p \not\mid (a-1)$, that the order is not 1.

So the order is $q$.

So $q | (p-1)$

Say we want to check if $2^n+1$ is a prime.

First of all $n$ could not contain a odd divisor, ortherwise say,

$$ n = q\cdot m $$

where $q$ is odd.

There is a factorization(if we set $2^n=x$),

$$ (2^n)^q+1=x^q+1=(x+1)(x^{q-1}-...+1) $$

So $n$ could only be of the form $2^k$

Now let’s say checking if $2^{2^n}+1$ is a prime,

Let’s check $n=4$, say there is a $p$

$$ p|2^{16}+1 $$

The same as,

$$ 2^{16} \equiv -1 \pmod p $$$$ 2^{32} \equiv 1 \pmod p $$

So,

$$ 32 | (p-1) $$

We only need to check $p=33,65,97,..$

Turns out all not divisible, so 65537 is a prime.

Diary 2026 08 30#