# Questions tagged [computational-number-theory]

Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.

320
questions

**17**

votes

**1**answer

602 views

### Possible contemporary improvement to bounded gaps between primes?

In his summary of his book Bounded gaps between primes: the epic breakthroughs of the early 21st century, Kevin Broughan writes
Which brings me to my final remark: where to next in the bounded gaps ...

**4**

votes

**0**answers

94 views

### Riemann-Siegel formula for Dirichlet characters

After unearthing and giving a proof of what is now known as the Riemann--Siegel formula for the Riemann zeta function enabling the computation of $\zeta(1/2+iT)$ in time $O(T^{1/2})$,
in 1943 Siegel ...

**-3**

votes

**1**answer

205 views

### Why wolfram alpha gives integers solutions for some equations of the form $ x^3 +(k\times10^n)^3 + z^3=0 $?

I have tried to get representations of some integers as sum of three cubic of the form $x^3+(k*10^n)^3+z^3$ with $k$ is integer and $n$ is a postive integer, I took this example : $(48807585839879)^3-(...

**3**

votes

**1**answer

116 views

### Connecting different ways of constructing cubic extensions of $\mathbb{Q}$

There are at least two ways to construct cyclic cubic extensions of $\mathbb{Q}$ as explained below. (A third one is given in the answer to an earlier question).
Given $A, B, C$ integers with $A\neq ...

**1**

vote

**0**answers

81 views

### Smooth number pairs satisfying a congruence

Let $\mathcal P=\{p_1,\dots,p_{2t}\}$ be $2t$ primes between $2^\ell$ and $2^{\ell+1}$ and fix an exponent bound $a\in\mathbb Z_{\geq2}$.
Fix $N\in\mathbb N$ whose prime factors $p$ satisfy $p>2^{\...

**0**

votes

**0**answers

79 views

### How to determine if a unramifed prime split or not?

Let $K$ be the Number field and $L$ be finite extension where $\mathfrak{p}$ prime of K is unramified. Are there any conditions on $\mathfrak{p}$ so that I can say $\mathfrak{p}$ splits completely in ...

**3**

votes

**0**answers

170 views

### Ramsey Numbers for Integers

Erdos defined $f(n)$ to be the minimum $r$ such that there is an $r$-coloring of the positive integers less than $n$, wherein $n$ cannot be written as the sum of distinct monochromatic integers. ...

**0**

votes

**0**answers

53 views

### Primality of $n$ bit integers in depth $n^\alpha$ under standard conjectures?

Denote $\mathsf{NC}(\mathsf{SUBLINDEPTH}(n),f(n))$ to be set of boolean circuits of fan-in $2$ which can be represented by depth $\cap_{\alpha>0}\mathsf{}n^\alpha$ and $f(n)$ sized Boolean circuits....

**21**

votes

**1**answer

718 views

### How to see that the determinant of this matrix is nonzero for all primes?

I'm trying to show that $\sum_{i = 0}^{p-2} (i+1)^{-1} t^{i+n}$ where $0 \leq n \leq p-2$ spans the vector space $\mathbb{F}_p[t]/(1-t)^{p-1}$ as a rank $p-1$ module over $\mathbb{F}_p$.
In other ...

**2**

votes

**0**answers

77 views

### On a result of Euler on pseudoprimes

In several sources (for instance on page 58 of the first ed. of Crandall & Pomerance book on prime numbers or at the end of this paper by J. H. Jaroma), I have seen a result that goes like this:
...

**1**

vote

**0**answers

45 views

### Hecke eigenvalues of Siegel Modular forms of level greater than two

I wish to compute Hecke eigenvalues of Siegel Modular forms of level greater than two using the software like SAGE OR MAGMA. Is it possible to do the same?

**0**

votes

**1**answer

62 views

### What are the complexity classes of these problems about divisibility and coprimality?

The problems
'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?'
'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ ...

**4**

votes

**0**answers

191 views

### What is the complexity class of this problem without Cramer's conjecture?

The problem 'Given $0<a<b$ is there a prime in the interval $[a,b]$?' is in $\mathsf{NP}$. If we assume Cramer's conjecture the problem is in $\mathsf{P}$ since if $b-a>(\log a)^{2+\epsilon}$ ...

**2**

votes

**0**answers

96 views

### Evidence of optimality of sieve algorithms

Sieve techniques apply to integer factoring and discrete logarithm to provide $2^{O(((\log n)(\log\log n)^2)^{1/3})}$ complexity for $n$ bit factoring and $n$ bit prime discrete logarithm.
The state ...

**2**

votes

**0**answers

37 views

### Asymptotic growth of the collection of Miller-Rabin pseudo-primes witnessed by a set

Consider a set $S$ of positive integers[*]. Define $P(S)$ as the set of numbers $N$ for which elements of $S$ are "witnesses" for the Miller-Rabin test for primality of $N$. Explicitly $P(S)=...

**1**

vote

**0**answers

104 views

### Diophantine approximation and the Euclidean algorithm

My question is whether something I've noticed is well-known. It seems like it must be, but I've been unable to find any references that describe what is outlined below.
Given real $x$ and irrational $...

**24**

votes

**2**answers

1k views

### Do these rational sequences always reach an integer?

This post comes from the suggestion of Joel Moreira in a comment on An alternative to continued fraction and applications (itself inspired by the Numberphile video 2.920050977316 and Fridman, ...

**8**

votes

**2**answers

1k views

### Fermat's last theorem $\pm1$

I'm planning a challenge over on Code Golf.SE about integers $a, b, c \ge 0$ such that
$$a^n + b^n = c^n \pm 1$$
for a given integer $n > 2$. However, I'm interested in whether any non-trivial ...

**2**

votes

**1**answer

73 views

### Software for $S$-unit equation

Is there any implementation available of an algorithm which solves in full generality the $S$-unit equation $x+y=1$ in a number field? It seems that Magma solves $ax+by=c$ but only in the algebraic ...

**11**

votes

**1**answer

244 views

### 4-cliques of pythagorean triples graph and its connectivity

Let natural numbers $a, b > 2$ be adjacent if $|a^2 - b^2|$ is a square number. One can find a 3-clique.
For example 153, 185, 697. The questions are: does there exist a 4-clique? Is this graph ...

**1**

vote

**0**answers

148 views

### Integer solutions of Diophantine equation $y^2= 1+4n^{\underline k} $

I am looking for the integer solutions for the diophantine equation $y^2 =4n(n-1)(n-2)\cdots (n-k+1)+1$ for a given $k$ where $n>k+1>5$.
In other words,
$$y^2=1+4n^{\underline k},\tag{I}$$
where ...

**3**

votes

**0**answers

45 views

### Reference: Asymptotic bit-complexity of algebraic operations and transcendental functions

This question is a reference request. Does anyone know of a reference that lists the asymptotic bit-complexity of algebraic operations and transcendental functions implemented on a Turing machine that ...

**0**

votes

**0**answers

29 views

### Points of bounded height in Magma/Sage

Suppose I have an irreducible curve $C\subseteq \mathbb P^2_K$, where $K$ is a number field, given by some equation $f(x,y)=0$. Is there any Magma command to search for points up to a given height on $...

**5**

votes

**1**answer

237 views

### Is there a short proof for the permutation invariance of this combinatorial map?

Consider a positive integer $n$ and integers $(c_i)_{1\le i \le 4}$, with $1 \le c_i \le n$. Conside the map:
$$f_n: (c_1,c_2,c_3,c_4) \mapsto \delta_{c_1,c_2}\delta_{c_3,c_4} - \# \{ |2n+1-2|x||, \ x ...

**9**

votes

**1**answer

626 views

### Prove that there are no composite integers $n=am+1$ such that $m \ | \ \phi(n)$

Let $n=am+1$ where $a $ and $m>1$ are positive integers and let $p$ be the least prime divisor of $m$. Prove that if $a<p$ and $ m \ | \ \phi(n)$ then $n$ is prime.
This question is a ...

**3**

votes

**1**answer

127 views

### Coppersmith bivariate polynomial roots implementation

Given $f(x,y)\in\mathbb Z[x,y]$ Coppersmith in https://link.springer.com/chapter/10.1007%2F3-540-68339-9_16 provides a provable method to find integer roots in polynomial time and this method was also ...

**0**

votes

**0**answers

90 views

### Common integer roots of polynomials

I have two polynomials of form
$$f_1(w,x)=M_1$$
$$f_2(y,z)=M_2$$
and I have two polynomials of form
$$g_1(w,x,y,z)=M_3$$
$$g_2(w,x,y,z)=M_4$$
where $f_1,f_2,g_1,g_2\in\mathbb Z[w,x,y,z]$ and $M_1,M_2,...

**7**

votes

**1**answer

601 views

### Expressing primes $p\equiv 1 \pmod 3$ in the form $p = x^2 + xy + y^2$

Fermat famously showed that the only primes $p$ of the form $x^2 + y^2$ are the primes such that $p \equiv 1 \mod{4}$. Furthermore, we now know “effective” versions of Fermat's theorem, i.e. given a ...

**5**

votes

**1**answer

220 views

### Inductively computing Mersenne primes / perfect numbers?

For two sets $A,B$ set $A+B = \{a +b | a \in A,b \in B\}$.
Let $(x_n)_{n \in \mathbb{N}}$ be independent variables. Let $\sigma(n)$ be the sum of divisors of $n$.
Set $\hat{\phi}(1) = \{x_1\}$ and ...

**3**

votes

**0**answers

72 views

### I have a question on the definition of 'good' primes in the paper of Cohen and Martinet

I'm reading the paper of Cohen and Martinet 'Etude heuristique des groups de classes'.
In the section 6, for an central idempotent $e$ of $\mathbb{Q}[\Gamma]$ and a prime $p$, the 'goodness' of $p$ is ...

**2**

votes

**1**answer

101 views

### When can we decompose a multivariable p-adic power series into product of single variable power series?

Is there any known result of decomposing multivariable power series over $p$-adic field into product of single variable power series ?
For example, consider the following power series in $n$ variables:...

**8**

votes

**1**answer

378 views

### Is it possible to find a (nonsquare) integer which is a quadratic residues modulo a given infinite list of primes?

I'm wondering if it's possible, given a prime p and an infinite list of primes $q_1$, $q_2$, ... to find an integer d which (1) is not a square mod p, but (2) is a square mod $q_i$ for all i. Always, ...

**0**

votes

**0**answers

21 views

### Eigenvector of $U |y \rangle \equiv |xy (mod N) \rangle$, when $ x \le N$ and $x, N$ coprimes

In the book quantum computing and quantum computation of Nielsen and Chuang, in the chapter relating to order-finding, they say that via a simple calculation, an eigenvector of $U |y \rangle \equiv |...

**5**

votes

**0**answers

293 views

### About a diophantine equation from group theory

Is there any set of odd primes $\{p_1, p_2,..., p_k\}$ and natural numbers $a_1,..., a_k$ such that the following equation satisfied:
$${p_1^{2a_1+1}+1 \over p_1+1}\times ....\times {p_k^{2a_k+1}+1 \...

**2**

votes

**2**answers

359 views

### A Pell like equation

If one takes in general $(\star)\, \,x^2-dy^2=C$ where $d$, $C$ in $\mathbb{N}$.
Taking $d=w^2p^2+p$ with $w\in \mathbb{Q}\ge 1$ and $p\in \mathbb{Z}$ which is verified (explained later), for the ...

**2**

votes

**0**answers

208 views

### Best known primality test for the whole intervals of integers up to $10^{20}$ — like the sieve of Eratosthenes

What are the best known primality test(s) for the whole intervals of integers up to $N=10^{20}$ ? "Best" means "have minimal amortized time per tested integer".
That is, the ...

**6**

votes

**1**answer

172 views

### On the density map of the abundancy index

Let $σ$ be the sum-of-divisors function. Let $σ(n)/n$ be the abundancy index of $n$. Consider the density map $$f(x) = \lim_{N \to \infty} f_N(x) \ \ \text{ with } \ \ f_N(x) = \frac{1}{N} \#\{ 1 \...

**2**

votes

**1**answer

85 views

### Estimation of a sum involving Stirling's number of second kind and binomial coefficient

Let $S(n, j)$ be Stirling's number of second kind. Let $p\in [0,1]$ and $m \in N$.
Bound from above the following sum:
$$
\sum_{j=0}^m S(n,j) {m \choose j}\, j! \, p^j
$$

**5**

votes

**3**answers

1k views

### Goldbach conjecture and other problems in additive combinatorics

The field is also known as additive number theory. I am interested in sums $z=x + y$ where $x \in S, y\in T$, and both $S, T$ are infinite sets of positive integers. For instance:
$S = T$ is the set ...

**3**

votes

**0**answers

76 views

### Minimum of a product of polynomial evaluated at primitive roots of unity, given that the value of the polynomial at the same lies on unit circle

This is something that came out of working on a problem:
Let $m$ be an odd positive integer and $f \in \mathbb Q[x]$ be a polynomial of degree less than $m$. With $\zeta_m$ denoting a primitive root ...

**1**

vote

**1**answer

191 views

### On a quadratic diophantine equation

Given a quadratic diophantine equation in $\mathbb Z[x,y,z]$ of form
$$ax^2+by^2+cx+dy+ez+f=0$$ are there standard methods to solve for it when $$\|(x^2,y^2,z)\|_\infty\leq e^{1/2}$$
$$\|(a,b,c,d,e,f)...

**2**

votes

**0**answers

75 views

### Elementary Iwasawa module

Let $k$ be a given number field. What is the importance and applications of knowing that the Iwasawa module $X_\infty$ of $k$ is an elementary $\Lambda$-module?

**1**

vote

**1**answer

184 views

### Integrality certification for product of two matrices $A B^{-1}$

Let's consider two non-singular integer matrices $A,B \in\mathbb{Z}^{n\times n}$. I want a test to check if $A\times B^{-1}$ is integral (or no denominators). I am referring the unimodular ...

**1**

vote

**2**answers

91 views

### For a given value of $n$ and $m$, find $\text{fib}(n)$ $\text{mod } m$ where $n$ is very huge. (Pisano Period) [closed]

Input
Integers $'n'$ (up to $10^{14}$) and $'m'$(up to $10^3$)
Output
$\text{Fib}(n)$ $\text{modulo}$ $m$
My questions
For example : Why $\text{fib}(n=2015)$ $\text{mod}$ $3$ is equivalent to $\...

**2**

votes

**0**answers

115 views

### Double Diophantine approximation

Let $0 < \alpha < 1$. For any $n$ there is a closest lower Diophantine approximation $\max p / q \leq \alpha$ with integer $0 \leq p < q \leq n$. It can be found efficiently, e.g., with Stern-...

**1**

vote

**0**answers

83 views

### On the smallest solution of a linear congruence

I have the following question. First, consider the following congruence for primes $p\geq 5$:
$24x\equiv -1\;(\mbox{mod}\;p)$.
The smallest $x$, that is, $1\leq x\leq p-1$ for which the above ...

**3**

votes

**1**answer

324 views

### Efficient computation of $\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor$

I need to compute efficiently the sum
$$
\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor.
$$
We can do this in $O({\sqrt{n}})$ but I need a faster algorithm: for example, it ...

**6**

votes

**0**answers

81 views

### Computing all eta quotients of given weight and level

I have written a rather naive program for finding all holomorphic eta quotients of
given weight and level (and varying character). When the level has few divisors it is
very fast, but incredibly slow ...

**1**

vote

**0**answers

73 views

### Digit summation of squared numbers

In olympiad teaching period, we have a session that students must try to design a good problem for others. Many times we arrive to good questions but sometimes there are some challenges. In one of our ...

**2**

votes

**0**answers

304 views

### The irrational numbers α such that n odd and m=⌊nα⌋ odd implies ⌊mα⌋ odd

This post is the analogous of that one (about $\sqrt{2}$) but with a much stronger expectation here.
We observed, and then this comment of Lucia proved, that for $\phi$ the golden ratio, if $n$ ...