Questions tagged [prime-factorization]

For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.

Filter by
Sorted by
Tagged with
3
votes
1answer
60 views

are there infinitely many primes $p,q$ such that $pq=a^2+b^4$

Are there infinitely many primes $p<q$, $p,q\neq 2,3$ such that $pq=a^2+b^4$ where $a,b\in \mathbb{Z}$ ? I've no idea if this is a very easy or very hard question. Any known result about this ? ...
0
votes
0answers
39 views

On the properties of the expansion into a sum of $4$ squares of the difference of squares of primes and composites

This question is about the properties of the expansion of $N= a^2-b^2 = (x_1^2+x_2^2+x_3^2+x_4^2)-(y_1^2+y_2^2+y_3^2+y_4^2)$ for primes and composite integers. The following examples will provide more ...
7
votes
1answer
60 views

What subset of the reals have unique prime factorizations if you allow rational exponents?

By the fundamental theorem of arithmetic we know that all positive integers have a unique prime factorization. So if $n$ is some positive integer, then $$n = \prod_{i\in\mathbb{N}}{p_i^{e_i}}$$ where $...
2
votes
1answer
65 views

Counting numbers smaller than $N$ with exactly $k$ *distinct* prime factors

Using common notation, $\omega(n)$ is the number of distinct prime factors on $n$. Similiarly, $\Omega(n)$ is the number of prime factors of $n$, not necessarily distinct: $120=2^{3}\cdot 3 \cdot 5$ , ...
-3
votes
1answer
60 views

What primes factor both $2$ and $3$, with no restriction on the domain? [closed]

What numbers (especially primes) factor both $2$ and $3$ (with no restriction on the domain)? How many answers are there? I'm looking preferably for a prime. My attempt: No natural number (other ...
0
votes
0answers
79 views

Why does $(a + 1)^p - (a)^p$ have so few prime factors? [closed]

Why does $(a + 1)^p - (a)^p$ have so few prime factors where $a$ is an positive integer and $p$ is any odd prime.
0
votes
0answers
22 views

Quadratic curves of integers $n=p_1^{k_1}\cdots p_l^{k_l}$ with $p_{i}$ $1\mod 3$ prime

Consider integers of the form $$n=p_1^{k_1}\cdots p_l^{k_l},$$ with $p_{i}$ primes which equal $1\mod 3$. With help of Mathematica, it seems that there exist quadratic families of subsets of values of ...
3
votes
0answers
35 views

Can we rule out $\ p\mid t\ $ , if $\ p\mid \phi_t(n)\ $?

Let $\ \phi_m(x)\ $ denote the $\ m\ $-th cyclotomic polynomial. For $\ n\ge 2\ $ define $\ t:=\phi_n(n)\ $ Must all the prime factors $\ p\ $ of $\ \phi_t(n)\ $ satisfy $\ p\equiv 1\mod t\ $ ? It ...
4
votes
0answers
152 views

Given three natural numbers $x, y, z.$ Prove that $xy+ yz+ zx\neq 462$ and $xyz+ x+ y+ z\neq 1193$

Given three natural numbers $x, y, z.$ Prove that Problem 1. $$xy+ yz+ zx\neq 462$$ without loss of generality, I accept $x:=\min\left \{ x, y, z \right \}\Rightarrow 3x^{2}\leq 462\Rightarrow x\leq ...
1
vote
0answers
30 views

Parity of (unique) number of prime factors

Analysis on the parity of the number of prime factors of an integer $n$ was performed. Here I displayed the parity as an random walk till $n=100.000.000$: Parity of the total number of prime factors (...
1
vote
3answers
75 views

Proving there do not exist natural numbers $m$ and $n$ such that $7m^2=n^2$

I'm stuck on my proof of this concept and I could use some help on understanding what to do next. Prove there do not exist natural numbers $m$ and $n$ such that $7m^2=n^2$ Proof will be by ...
0
votes
1answer
26 views

Totient minimal value for semiprimes

I have two question concerning Euler Totient of semiprimes. First question : given $N=p_1 * p_2$ and $M=p_3*p_4$ where $p_1,p_2,p_3,p_4$ are prime numbers greater than 5; and $M>N$ this means that ...
1
vote
0answers
27 views

Probability a random number $M$ is a not a factor of $N$

Let $N$ be some positive integer and let $S := \lbrace 1, 2, \cdots, \log^2(N) \rbrace$ (pretending at $\log^2(N)$ is an integer). Suppose $M$ is randomly chosen from the set $S$. The goal is to use ...
5
votes
0answers
89 views

Prove that there is an infinite number of values of $n$ for which the biggest prime divisor $p$ of $2^{n}-1$ satisfies $p < 2^{n/2021}-1$

Prove that there is an infinte number of positive integers $n>1$ for which the biggest prime divisor of $2^n-1$ is smaller than $2^\frac{n}{2021}-1$ (which may or may not be integral). I tried to ...
2
votes
1answer
38 views

How to find the number of compound divisors of the smallest product from two unknown numbers?

The problem is as follows: The number of panadol pills at a pharmacy is a positive whole number that it has two prime divisors and 45 positive divisors. The number of tylenol pills at the same ...
0
votes
1answer
57 views

Using Euler's Totient Function, how do I find all values n such that, $\varphi(𝑛)=14$

I just recently started working with Euler's Totient Function, and I came across the problem of solving for all possible integers $n$ such that $\varphi(n)=14$. I know there are similar questions with ...
4
votes
2answers
105 views

Is the following producing a list of all prime numbers without skipping in a consecutive order?

The following consecutive list is made as a table with the following columns : column 1 column 2 column 3 $A$ $B=(A^2 -1) / 6$ prime factors of $B$ Where $A$ is odd and $A \mod 3 ≠ 0$ Example: $A = ...
0
votes
1answer
35 views

Why Is there no consistent factor in $A^2$ versus the other $A^X$ In the following sequence?

The following sequence is built of $((A^z)^x -1)/6$ where $z$ increases by $1$ and the conditions for $A$ must be that $(A - 1) \mod 6 = 0$ and for $x$ must be that $x$ is odd and $x > 1$: $((A^1)^...
5
votes
2answers
81 views

Combinatorics on divisors

Consider the set $D$ of all divisors of $10000$. What is the number of subsets $H \subseteq D$ containing at least two elements such that for every $a, b \in H$, $a \mid b$ or $b \mid a$? I tried ...
0
votes
1answer
56 views

A simple problem on Finding factors

There's a question wherein we have to find the number of factors of $480$ of the form $8n+4$ where $n \geq 0$. Now, the prime factorisation of $480$ gives $2^5 \times 3 \times 5$. This is to be of the ...
1
vote
0answers
35 views

Factoring Integers, question on Wiki algorithm

I have questions on the integer factorization algorithm described on Wiki. The Wiki description is heavy English and I translated it so it's more symbolic. My question is if this translation makes ...
1
vote
0answers
29 views

Factor the Outputs of a Quadratic using Sieving

I want to factor $(n-1)^3+1$ for many values of $n$. Meaning, for every value of $n$ from $1$ to $N$ for some large $N$ I want a list of prime factors and corresponding powers for $(n-1)^3+1$. We ...
0
votes
1answer
32 views

How can I prove that the results in the following sequence will always share the same factor?

The following sequence is built of $((A^z)^x -1)/6$ where $z$ increases by $1$ and the conditions for $A$ must be that $(A - 1) \mod 6 = 0$ and for $x$ must be that $x$ is odd and $x > 1$: $((A^1)^...
1
vote
1answer
76 views

What's Special about Rowland’s Prime-Generating Sequence?

Recently I asked this question and quickly got back some excellent responses. I asked the question because I came across a paper by Eric Rowland called "A Natural Prime-Generating Recurrence"...
15
votes
2answers
256 views

Is there a positive integer $n$ such that the prime divisors of $n^3 - 1$ are $2$, $3$ and $7$?

For a positive integer $k$ write $\pi(k)$ for the set of all prime divisors of $k$. For example, $\pi(24) = \{2,3\}$ and $\pi(1) = \emptyset$. Question. Is there a positive integer $n$ for which $\...
14
votes
1answer
443 views

Largest consecutive integers with no prime factors except $2$, $3$ or $5$?

The number $180$ has a special property. Its prime factors are only $2$, $3$, and $5$. However the number $220$ does not have this special property because one of its prime factors is $11$. In the ...
3
votes
0answers
81 views

Do the sequences defined by $a_n=a_{n-1}+(\text{the least prime factor of }a_{n-1})+1$ starting with $2,6,14,\ldots$ merge?

Let $S_k$ be the sequence defined by $a_k(1)=k,\ a_k(n)=a_k(n-1)+(\text{the least prime factor of }a_k(n-1))+1$. A diagram of these sequences for around $k<100$ is shown below. As you can see, $S_3$...
0
votes
0answers
44 views

Why is time complexity of factoring expressed for $2^n$ and not $N$?

The question I have is what is in the comment of the question: Why is the time complexity of factorization $2^n$? The original author didn't mention why we are considering the input size in bits and ...
0
votes
1answer
111 views

I have almost no idea how to factor numbers this big. [closed]

$14425638854646469646839767613420413647898432138735230192512819$ is the product of two prime numbers. Each factor is an answer. I have to give both factors as answers. How would I get to them and ...
1
vote
1answer
16 views

Number of different ways you can place positive integers into an array of size N such that the product of the integers is K

To find the number of ways to place positive integers into an array of size $N$ such that the product of the numbers is $K$. So the problem boils down to finding the numbers of ways to place the prime ...
3
votes
0answers
87 views

Does the mean of $\log{\text{gpf}(n)}/\log{n}$ for the first $n$ naturals have a lower bound?

Does $$\frac{1}{n-1}\sum_{i=2}^{n}{\frac{\log{\text{gpf}(i)}}{\log{i}}}$$ have a lower bound as $n\rightarrow\infty$? Here, $n\in\mathbb N$ with $n>1$, and gpf returns the greatest prime factor of ...
2
votes
1answer
155 views

On the greatest prime factor of $p^2+1$, $p\in\mathbb{P}$

Are there infinitely many pairs $(p,q)\in\mathbb{P}^2$ such that $p>q$ and $p\mid q^2+1$? This is a very interesting. There are many methods for bounding the greatest prime factor of $n^2+1$, but ...
1
vote
0answers
47 views

Question on strong Goldbach conjecture

Lately I realized that strong Goldbach conjecture could be "reduced" to show that every even composite number with more than two prime factors (not necessarily distinct) can be expressed as ...
2
votes
1answer
57 views

Number of integers at most $x$ with exactly two distinct prime factors

I wish to find an asymptotic for the number of integers not exceeding $x$ with exactly two distinct prime factors. Here is a starting point: Throughout $p$ and $q$ are primes. We are interested in $\...
22
votes
2answers
387 views

Is the “cyclotomic diagonalization” always squarefree?

For every integer $n\ge 2$ , define $$f(n):=\Phi_n(n)$$ where $\Phi(n)$ is the $n$ th cyclotomic polynomial. This can be considered as the "cyclotomic diagonalization" Prove or disprove the ...
1
vote
0answers
22 views

Possible extensions of the triangular structures in Gilbreath's conjecture to tetrahedronic structures.

Gilbreath's conjecture produces an triangular matrix of witch the most elements are either $0$, or $2$. When using different colors for those two elements, very interesting triangular structured trees ...
2
votes
0answers
48 views

Non-constant polynomial over an integral domain without any irreducible factors.

Let $R$ be an integral domain. I am trying to find a $f \in R[x]$, such that $\deg(f) \geq 1$, and $f$ does not have any irreducible factors in $R[x]$. Does such $f$ exist? Though I haven't been able ...
2
votes
2answers
80 views

Validity of challenge to common Euler product derivation strategy (infinitely long denominator prime factorisations)

Background The following Euler product for the Riemann zeta function is well known. $$ \sum_n \frac{1}{n^s} = \prod_p (1-\frac{1}{p^s})^{-1} $$ Here $n$ ranges over all integers, $p$ over a primes, ...
2
votes
0answers
69 views

Product of two sums of inverses of primes

I want to prove that for all $p_1,..., p_k$, $q_1,...q_l$ distincts prime numbers, this equality is false : $$\left( \sum_{i = 1 }^k \frac{1}{p_i} \right) \left( \sum_{j=1 }^l \frac{1}{q_j} \right) =...
0
votes
0answers
79 views

Prime factors of $a$ and $a+1$

Quick question Is there any pattern to how a number's prime factors change when you increase it by $1$? Is there any way you can predict a number's prime factors based on the factors of its previous ...
3
votes
1answer
60 views

Possible Values of # of Ordered Factorization of Integers

I was trying to find the number of ordered factorizations of integers into parts $\gt 1$. Starting with $0$, the number of ordered factorizations of $n$ forms this sequence. Interestingly, and in ...
1
vote
0answers
40 views

Can We Speak of the “Prime Factorizations” of the Positive Rationals?

I am of two minds with respect to this question; therefore I will lay out the case for the existence of prime factorizations of positive rationals such as $2.5$ or $\frac{22}{7}$, and then I will lay ...
1
vote
1answer
30 views

General form for this integer-factor-shifting bijection?

Let $f(k,s)$ be a function that takes all the factors in an integer $k$ and increases their prime indices by $s$. e.g. $$f(28,2)=f(2^2 \cdot 7,2)=f(p_1^2 p_4,2)=p_3^2 p_6 =5^2 \cdot 13=325.$$ I've ...
1
vote
3answers
56 views

Finite Factors of Refactorable Numbers

This was just a question that I came up with while learning about refactorable numbers. While looking through the sequence of refactorable numbers (1, 2, 8, 9, 12, 18....), I decided to look at the ...
1
vote
0answers
50 views

Does a Prime Number $p_k$ Have a Prime Factorization (Where the Factorization Is $p_k$ Itself)?

On one hand, we can think of the prime factorization of positive integer $n$ as representing $n$ by a product of prime numbers, each being smaller than $n$. In that sense, a prime number $p_{k}$ ...
3
votes
1answer
71 views

Proof that each prime power of ${2n \choose n}$ is $\leq \log_p 2n$

I'm trying to work through this proof of the prime number theorem. Def: Let $P_p(x)$ be the prime power of $p$ in the prime factorization of $x$. I.e. for any natural number $x$, $x = \prod_{p\in \...
1
vote
1answer
45 views

When is the number of Divisors of a Number equivalent to one of its Factors?

My math teacher asked me this problem for homework and I am unsure how to solve it. Which numbers contain a number of factors equivalent to the value of one of their divisors? I found that 8 works, ...
1
vote
0answers
18 views

General Number Field System Factorization (GNFS) RFB, AFB, QCB Step Question

Ok, from the document page 16 example at: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.219.2389&rep=rep1&type=pdf which states: Any algebraic factor base A can be represented by ...
1
vote
1answer
134 views

A prime problem in Fibonacci sequence

This problem can be a little too wild but have at it anyways: Prove that for every positive integer $n$ $\geqslant$ $7$ , $f_{n+1}$ has a prime divisor that doesn't divide $f_{n}-1$ where $f_{n}$ is ...
1
vote
2answers
41 views

Reduce power modulo a semiprime quickly by hand

I worked through problem 7 in this GRE prep material (https://math.uchicago.edu/~min/GRE/files/week1.pdf), and I got the right answer, but I'm wondering if there is a more efficient way to do this, ...

1
2 3 4 5
36