# Tagged Questions

**0**

votes

**2**answers

452 views

### On reducible polynomials with positive coefficients, $1$ as constant coefficient and certain bounds on coefficients

Given $a \in \mathbb{Z}$ with $a > 1$. Let $g(x) \in \mathbb{Z}[x]$ be a polynomial with $g(a)=\pm 1$. Let $h(x) \in \mathbb{Z}[x]$ be a polynomial with $h(a)= p$, a prime. Let $g(x)$ and $h(x)$ ...

**12**

votes

**3**answers

1k views

### Is there a composite number that satisfies these conditions?

We know that if $q=4k+3$ ($q$ is a prime), then $(a+bi)^q=a-bi \pmod q$ for every Gaussian integer $a+bi$. Now consider a composite number $N=4k+3$ that satisfies this condition for the case ...

**3**

votes

**3**answers

364 views

### Proving a least prime factor

Suppose that I find a small prime factor $p$ dividing a large number $n$ and I wish to prove that it is the least prime dividing $n$. There are two obvious approaches: either factor $n/p$, or divide ...

**8**

votes

**1**answer

268 views

### Does this notion of pseudoprime relative to a matrix appear in the literature?

Let $M$ be a square matrix with integer entries. Then Fermat's little theorem for matrices holds:
$$\text{tr}(M^p) \equiv \text{tr}(M) \bmod p.$$
This follows by an examination of the action of the ...

**11**

votes

**2**answers

650 views

### Saying things rapidly about integer factorisations

Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or ...

**1**

vote

**0**answers

324 views

### Witt rings and prime number generator?

Let $p$ be a fixed prime number. We define the ring of Witt vectors $W(R)$ for any commutative ring $R$ as follows:
For every ring morphism $R \rightarrow R'$ the induced morphism $W(R) \rightarrow ...

**2**

votes

**0**answers

258 views

### Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...

**2**

votes

**1**answer

1k views

### How many cpus needed to check a 100 million digit prime number efficiently? [closed]

If I had access to potentially unlimited CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped ...

**1**

vote

**1**answer

316 views

### Calculating the constant in the Bateman-Horn-Stemmler conjecture

Bateman & Horn [1], building on Bateman & Stemmler [2], give a conjectured formula for the density of numbers that produce simultaneous primes in a number of fixed polynomials.
The constant ...

**6**

votes

**2**answers

856 views

### Recovering n from sigma(n)/n

For any positive integer $n$, we define
$$\sigma(n) := \sum_{d \mid n} d,$$
and
$$\delta(n) := \frac{\sigma(n)}{n} = \sum_{d \mid n} \frac{1}{d}.$$
Is there an (efficient) way to determine ...

**12**

votes

**1**answer

539 views

### Analytic lower bounds on the first sign change of pi(x) - li(x)?

There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...