Articles of number theory

bound of the number of the primes on an interval of length n

I made this observation and it seems reasonable to me to ask :if $n$ is a natural number then the number of the primes less than or equal to $n$ is denoted by $π(n)$ . is that true that in any interval of length $n$ there are at most $π(n)+1$ primes?(the $+1$ is needed for […]

Hensel Lifting and solving with mods

I need to use the Hensel-Newton method (aka Hensel Lifting) to find all solutions of: $$x^2 + x + 47 \equiv 0\:(\text{mod } 343)$$ Note: $$ 343 = 7^3 $$ I don’t really understand Hensel Lifting so I am not sure where to begin. Can someone help give me a better understanding of Hensel Lifting […]

Asymptotic for primitive sums of two squares

A positive integer $n$ can be written primitively as the sum of two squares, meaning $n = x^2 + y^2$ with $\gcd(x,y)=1,$ precisely when $n$ is not divisible by $4$ or by any prime $q \equiv 3 \pmod 4.$ Since this applies to primes $p \equiv 1 \pmod 4,$ the count of such numbers up […]

How to find all $m,n$ such that $mn|m^2+n^2+1$?

How to find all positive integers $m,n$ such that $m|n^2+1$ and $n|m^2+1$ ? My work:- Let $n^2+1=mk , m^2+1=ng$ , then $mkg=gn^2+g=m^2n+n+g$ , hence $m|n+g$ i.e. $m|n+\dfrac{m^2+1}n$ i.e. $\dfrac{n^2+m^2+1}{mn}$ is an integer i.e. $mn|m^2+n^2+1$ . Now conversely assume $mn|m^2+n^2+1$ , then $m|m^2+n^2+1$ and $n|m^2+n^2+1$ i.e. $m|n^2+1$ and $n|m^2+1$ So the question equivalently asks to positive […]

All natural solutions of $2x^2-1=y^{15}$

How can I find all positive integers $x$ and $y$ such that $2x^2-1=y^{15}$? PS. See here.

Question about quadratic twists of elliptic curves

Let $E$ be an elliptic curve and $d$ be a squarefree integer. If $E’$ and $E$ are isomorphic over $\mathbb{Q}(\sqrt{d})$, must $E’$ be a quadratic twist of $E$?

Whether the map $x\mapsto x^3$ in a finite field is bijective

Suppose $p\in\mathbb{Z}$ is prime and $\mathbb{F}_p:=\mathbb{Z}/p\mathbb{Z}$ is the finite field of size $p$. Now, consider the map: $$f:\mathbb{F}_p \to \mathbb{F}_p$$ given by $f(x)=x^3$. Then, (1) What are the values of $p$ for which $f$ is bijective ? (2) What are the values of $p$ for which $f$ is injective/surjective ? EDIT: I came up with […]

Profinite and p-adic interpolation of Fibonacci numbers

On the topic of profinite integers $\hat{\bf Z}$ and Fibonacci numbers $F_n$, Lenstra says (here & here) For each profinite integer $s$, one can in a natural way define the $s$th Fibonacci number $F_s$, which is itself a profinite integer. Namely, given $s$, one can choose a sequence of positive integers $n_1, n_2, n_3,\dots$ that […]

Eulers totient function divided by $n$, counting numbers in the set that are coprime to n

If we divide Euler’s totient function $\omega(n)$ by $n$, we obtain a fraction. If we multiply this fraction by any natural number $m$ which gives us another natural number $p$, is it true that $p$ is the number of natural numbers in $[1,m]$ that are coprime to $n$?

Smallest number $N$, such that $\sqrt{N}-\lfloor\sqrt{N}\rfloor$ has a given continued fraction sequence

How can I find the smallest positive integer $N$, such that the continued fraction of $\sqrt{N}-\lfloor\sqrt{N}\rfloor$ begins with a given finite sequence containing a zero followed by positive integers ? For example, the sequence $[0,1,2,3,4]$ is given. We have to find the smallest number $N$, such that $\sqrt{N}-\lfloor\sqrt{N}\rfloor$ begins with $[0,1,2,3,4]$. The number $\sqrt{388}-\lfloor\sqrt{388}\rfloor$ has […]