All Questions
44 questions
0
votes
0
answers
78
views
Factoring totient of a prime
Is it any easy to factor $p-1$ when $p$ is a prime compared to general factorization problem?
What about when $2p+1$ is also a prime?
- 13.9k
4
votes
0
answers
266
views
How dense are quotients of smooth numbers?
As usual, call a positive integer $y$-smooth if it has no prime factors greater than $y$. Write $S(x,y)$ for the set of $y$-smooth integers $\leq x$. Write $R(x,y)$ for the set of quotients $\{a/b: a,...
- 20.2k
9
votes
3
answers
9k
views
Algorithm for detecting prime powers
While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...
- 1
1
vote
0
answers
60
views
On the parity of $(2^{\varphi(n)}-1) \bmod{n^2}$
For odd integer $n$ define the function
$$ J(n)=(2^{\varphi(n)}-1) \bmod{n^2}$$
$J(n)$ is integer in $[0,n^2-1]$ and it is divisible by $n$.
Integer $n$ is Wieferich number
iff $J(n)=0$ and if $n$ is ...
- 25.4k
6
votes
2
answers
804
views
Must Mersenne numbers be divisible by arbitrary large primes with exponent one?
Let $M_n$ denote the Mersenne numbers $M_n=2^n-1$.
As $n$ varies, must $M_n$ be divisible by arbitrary large prime $p$
with exponent one, i.e. $p \mid M_n, p^2 \nmid M_n$?
In other words, must the ...
- 44.4k
10
votes
4
answers
1k
views
The smallest solution to $2^{2k}-1=\text{powerful}$
Integer is powerful if all the exponents in its factorization are at least $2$.
Every powerful integer can be written in the form $a^2 b^3$.
For odd $k$, define $F(k)=2^{2k}-1=(2^k-1)(2^k+1)$.
This ...
- 44.4k
1
vote
0
answers
128
views
Effective Erdős–Kac theorem
I have some number $N$ and some integer $k>0$. I want to know what fraction of numbers up to $N$ have more than $k$ prime factors. (In my application, with repetition, but the $\omega$ version is ...
- 9,114
10
votes
1
answer
315
views
Fixpoints of $m\longmapsto \mathrm{rad}(\phi(m^2))$ under iteration
Given a strictly positive integer $m$ let $\alpha(m)=\mathrm{rad}(m\phi(m))$
be the radical (product of all distinct prime divisors) of the product of $m$ and of Euler's totient function $\phi(m)=m\...
- 105k
5
votes
0
answers
160
views
Reducibility of $f(x)^{2^n}+1$ and $f(x)^{2^n}+g(x)^{2^n}$
Related to generalized Fermat numbers.
Let $f(x),g(x)$ be coprime polynomials with integer coefficients.
Assume that if $f(x)$ or $g(x)$ are of the form $h(x)^k$ then $k$ is power
of two.
Q1 Is it ...
- 25.4k
6
votes
0
answers
169
views
$p^2+a^2$ can be a squarefree number with all prime divisors less than $p$?
Let $p$ be a prime $\ge 31$.
Is there an integer $a < p$ such that $p^2 + a^2$ is a squarefree and all of its prime divisors are less than $p$?
For example, for $p=31$, $31^2+5^2 = 986 = 2 \times ...
- 483
118
votes
5
answers
33k
views
How did Cole factor $2^{67}-1$ in 1903?
I just heard a This American Life episode which recounted the famous anecdote about Frank Nelson Cole factoring $N:=2^{67}-1$ as $193{,}707{,}721\times 761{,}838{,}257{,}287$. There doesn't seem to be ...
- 20.2k
2
votes
0
answers
70
views
Twin prime distribution centering twice a semiprime
What is the conjectured distributional behavior of semiprimes $pq$ ($p$ and $q$ are primes) having the property $2pq+1$ and $2pq-1$ are primes?
- 13.9k
1
vote
0
answers
65
views
Distribution of number of prime factors of $p^k\pm1$
What is the behavior of number of prime factors of integers of form $p^k\pm1$ where $p$ is a fixed odd prime or $2$ and $k$ varies over positive integers?
- 13.9k
1
vote
0
answers
107
views
Polynomial divisible by unbounded primes with exponent one
Let $f(x)$ be squarefree polynomial with integer coefficients and
degree at least $3$.
Is it true that for all sufficiently large $n$, $f(n)$ is divisible
by prime $p$ with exponent one and $p$ is ...
- 25.4k
1
vote
1
answer
181
views
On the sequence $a(n)=\gcd(2^n-1,\phi(2^n-1))$
For natural $n$, define the sequence
$$
a(n)=\gcd(2^n-1,\phi(2^n-1))
$$
It doesn't appear to be in OEIS and starts
$1,1,1,1,9,1,1,1,3,1,9,1,3,1,1,1,27,1,75,49$
Q1 Can we unconditionally prove $a(n)=1$...
- 109k
2
votes
2
answers
406
views
When is a prime factor of Mersenne number Wieferich prime?
Wieferich prime is a prime number $p$ such that $p^2$ divides $2^{p - 1} - 1$.
There are only two Wieferich primes known and it is an open problem if
there are infinitely many non-Wieferich primes.
...
- 1,362
9
votes
1
answer
698
views
Hensel's lemma, Bezout's identity, and the integers
Factorization in the ring $\mathbb{Z}[x]/(x^2+1)\mathbb{Z}[x]\cong \mathbb{Z}[i]$ is well known. For instance, $5$ and $13$ (and any prime $\equiv 1\pmod{4}$) are no longer prime.
The factorization ...
- 18.7k
1
vote
0
answers
178
views
Need help interpreting this formula for the number of Goldbach partitions [closed]
1: Formula for the number of Goldbach partitions.
Let $g\left(n\right)$ denote the number of Goldbach partitions of even integer $2n$:
$$g_{\left(n\right)}=\sum_{3\leq p\leq2n-3}\left[\pi\left(2n-p\...
- 197
4
votes
1
answer
325
views
Numbers with large prime exponents and the ABC conjecture
By Fermat's Last Theorem, there are no solutions to the Diophantine equation $a^n + b^n = c^n$ for $a,b,c > 0$ and $n>2$. Beal's conjecture allows the exponents to be different (but also $>...
- 148k
1
vote
0
answers
96
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^{\...
- 13.9k
0
votes
1
answer
184
views
Upper bound for tuple of exponents of prime factorization
Let $a(n)$ be the $k$-ary tuple of the exponents of the prime factorization of $n$. For example,
$$a(5184)=a(2^{6}⋅3^{4})=(6, 4), a(65536)=a(2^{16})=(16).$$
Formally, let $p_{1}^{a_{1}}, p_{2}^{a_{2}...
- 105k
5
votes
2
answers
308
views
Updates on a least prime factor conjecture by Erdos
In the 1993 article "Estimates of the Least Prime Factor of a Binomial Coefficient," Erdos et al. conjectured that
$$\operatorname{lpf} {N \choose k} \leq \max(N/k,13)$$
With finitely many ...
- 30.1k
1
vote
0
answers
133
views
Primes which do not divide certain homogeneous polynomials
It is known that if $x^2 + y^2 = z^2$ is a primitive Pythagorean triplet then $z$ is not divisible by any prime of the form $4k-1$. The following is a generalization of this classical result which ...
- 5,470
3
votes
0
answers
323
views
If $p^2 - q^2$ is a perfect square where $p$ and $q$ are primes $> 5000$ then is one of its prime factors always greater than $17$? [closed]
Is it true that if $p^2 - q^2$ is a perfect square where $p$ and $q$ are primes $> 5000$ then it has a prime factor greater than $17$?
Note: This question was asked in MSE but did not receive an ...
- 5,470
2
votes
1
answer
231
views
Equations involving arithmetic functions of primorials
Let $\sigma(n)=\sum_{1\leq d\mid n}d$ the sum of divisors, $\varphi(n)$ the Euler's totient function and we denote the primorial $\prod_{k=1}^n p_k$ as $N_n$, where $p_k$ denotes the $k$-th prime ...
5
votes
0
answers
501
views
Factorizations as a product of primes minus one
Let $x$ be a positive rational number. I am interested in factorizing $x$ as a product of primes minus one. In fact, I would also like make sure the primes in the decomposition are distinct, and I ...
CommunityBot
- 1
20
votes
1
answer
2k
views
Circle $x^2 + y^2 = n!$ doesn't hit any lattice points for any $n$ except for $0$, $1$, $2$ and $6$ or does it?
I stumbled across the following problem in high school:$$
x^2 + y^2 = n!
$$
I tested it within my laptop capabilities, watched a 3b1b video Pi in prime regularities, where he explains how to find the ...
- 1,459
5
votes
0
answers
161
views
Consecutive integers each of which has a large prime factor
There are many results about consecutive integers all having small prime factors. But what about consecutive integers each of which has a large prime factor?
More precisely, let $P(n)$ be the ...
- 341
2
votes
2
answers
1k
views
What is the natural density of hyper prime numbers?
What do we mean by hyper prime numbers? Well, roughly speaking they are natural numbers which are prime with respect to hyperoperators in arithmetic such as exponentiation, tetration, pentation, et ...
CommunityBot
- 1
1
vote
1
answer
144
views
Factoring with partial information on gaps
If $N=PQ$ is a semi-prime with $P=N^{\frac12 +\delta}$ and $Q=N^{\frac12-\delta}$ then if we know $\delta\in(0,\frac12)$ to a reasonable precision we can factor $N$ quickly. What precision (number of ...
CommunityBot
- 1
4
votes
0
answers
408
views
Can we efficiently factor $n$ given that $n=pq$ where $p,q$ are primes satisfying $p=a^2+b^2, q=2ab+1$ for some $a,b$
Suppose we're given a particular number $n \in \mathbb{N}$.
We're also given that $n=pq$ where $p,q$ are unknown primes satisfying
$$
p=a^2+b^2
$$ and
$$
q=2ab+1
$$
for some $a,b$.
Is there an ...
- 141
2
votes
1
answer
347
views
Which composites pass this probabilistic primality test?
If a composite integer resembles a prime too closely, it must pass
algorithmic tests designed to find primes and in addition avoid nontrivial
factorization.
Given an integer $p$, assume it is prime ...
- 30.5k
3
votes
2
answers
932
views
Hilbert Numbers
A positive integer $n$ is called a Hilbert number if $\exists a,b,d \in \mathbb{N}$ such that $ 4ab-a-b = d n$ and $d|a b$.
I ran an algorithm checking divisors for all $0\lt a,b\le500$, and the ...
- 34.3k
7
votes
1
answer
382
views
$\log \log p / \log \log n$, where $p|n$, gets equidistributed in [0,1] (for almost all $n$)
According to Hardy-Ramanujan/Erdős-Kac we know that usually there are $\sim\log\log n$ prime numbers in a factorization. But if you pick up a natural number at random, and you factor it, what is the ...
- 105k
2
votes
1
answer
332
views
Upper bound for product of exponents of prime factorization
Let $p(n)$ be the product of the exponents of the prime factorization of $n$. For example,
$$p(5184)=p(2^{6}\cdot 3^{4})=24,\qquad
p(65536)=p(2^{16})=16.$$
Is $p(n) = O(\log^{k}(n))$ for some constant ...
- 105k
27
votes
4
answers
2k
views
Structures in the plot of the “squareness” of numbers
(This is based on an earlier MSE posting,
"Structures in the plot of the “squareness” of numbers.")
My main question is to explain the structural features of this plot:
This is a plot of what I call ...
CommunityBot
- 1
2
votes
1
answer
450
views
Is there a "small $\omega$" number theorem?
In my studies of how primes jump (search this forum for a link), a question has been raised which may have been studied. Can anyone jump-start my literature search with references regarding the ...
7
votes
1
answer
1k
views
Results on the largest prime factor of $2^n+1$
A work of Cameron Stewart (the paper has appeared in Acta Mathematica), proving a conjecture of Erdos, Stewart shows that
the largest prime factor of $2^n-1$ is at least
$n \times \exp\Big( \frac{\...
- 4,746
4
votes
1
answer
151
views
Reference Request on the existence of $k$ satisfying $P(\Phi_d(2))^k \gt \Phi_d(2)$ for all $d$
I am working my way through the literature regarding the following conjecture: There is a positive integer $k$ such that for all positive integers $d$,
$$P(\Phi_d(2))^k \gt \Phi_d(2).$$
I am ...
- 19.6k
4
votes
0
answers
279
views
Analog of Euler's factoring technique
Is there an analog of Euler's Two Squares factoring theorem over polynomial rings $\Bbb Z[x]$ by considering a version for non-negative polynomials?
Euler's two squares factoring states that numbers ...
- 13.9k
7
votes
1
answer
2k
views
The number of distinct prime factors of $n\in\mathbb N$
Let $\omega(n)$ be the number of distinct prime factors of a natural number $n$.
Note that $\omega(n)=0\iff n=1$, and that $\omega(24)=\omega(2^3\cdot 3^1)=2\ (\not = 4)$.
(For more details, you can ...
CommunityBot
- 1
3
votes
3
answers
696
views
For any prime $p$, is there $C$ such that if $x\ge C$, then all but one integer among $x+1, x+2, \dots, x+p$ has Greatest Prime Factor $> p$
I apologize if this is a naive question about greatest prime factors (gpf). I was thinking about the sequence of integers where $\mathrm{gpf}(x) \le p$ where $p$ is any prime.
Clearly, as $x$ ...
- 6,210
15
votes
2
answers
1k
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 ...
- 2,913
1
vote
2
answers
2k
views
find the minimum difference between the factors of a number
Given a number c, what is the smartest way to find |x - y| such that x * y =c and |x - y| is minimum
- 376