Questions tagged [prime-factorization]
For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.
2,081
questions
-2
votes
0
answers
22
views
Proof factorization problem is Co-NP [closed]
I'm looking for the proof that factorization problem is Co-Np where Co-NP problems are those which their complement is in NP.
To be more clear, factorization has a decision problem which is provided ...
-1
votes
0
answers
31
views
Primes (i.e irreducibles) have no nontrivial factorizations. [duplicate]
I am reading Herstein and it makes the following claim.
The sentence followed by the definition is what I don't get.
A prime element $\pi \in R$ has no non-trivial factorisation in $R$.
By definition,...
3
votes
1
answer
178
views
Smallest "diamond-number" above some power of ten?
Let us call a positive integer $N$ a "diamond-number" if it has the form $p^2q$ with distinct primes $p,q$ with the same number of decimal digits. An example is $N=10^{19}+93815391$. Its ...
0
votes
0
answers
37
views
Finding square root modulo $n$ and factorization of $n$ [duplicate]
I have this task to prove that the factorization of number $n = p \cdot q$ (where $p$ and $q$ are prime) task is equivalent to finding square root module n.
I have found this lecture that explains the ...
2
votes
2
answers
42
views
Does the monoid of non-zero representations with the tensor product admit unique factorization?
Let $(M, \cdot, 1)$ be a monoid. We will now define the notion of unique factorization monoid. A non-invertible element in $M$ is called irreducible if it cannot be written as the product of two other ...
1
vote
2
answers
71
views
Expected number of factors of $LCM(1,…,n)$ (particularly, potentially, when $n=8t$)
I’m trying to prove something regarding $8t$-powersmooth numbers (a $k$-powersmooth number $n$ is one for which all prime powers $p^m$ such that $p^m|n$ are such that $p^m\le k$). Essentially, I have ...
0
votes
0
answers
38
views
Converting a Quartic Term into Quadratic Form in QUBO for Prime Factorization
I'm trying to embed the prime factorization problem into the form of a QUBO. To do so, let $p$ and $q$ be two real positive numbers. We can represent these two numbers as binary numbers, which itself ...
0
votes
0
answers
26
views
Matrix Representation for Prime Factorization in QUBO Form
I'm trying to reproduce a paper on Prime Factorization. This paper converts the prime factorization problem into a QUBO form, which then we can map it to the Ising model.
As an example, let $p$ and $q$...
1
vote
1
answer
62
views
Find the next "consecutive-prime composite number" from a given one.
Good day all. I am not a mathematician by a long shot. Please bear with me...
I am playing with "descending-consecutive-prime composite numbers" (I don't think that's the term). These are ...
1
vote
0
answers
42
views
Factoring ideals into prime ideals
I am currently working on a problem from the book “Introductory Algebraic Number Theory” by Kenneth S. Williams and Saban Alaca, and I would like to verify my solution.
The problem is:
Factor $<6&...
1
vote
1
answer
99
views
distribution of square roots of unity $mod n$ | Factoring with inverse pair
I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where
$$ dc \equiv 1 \pmod{\phi(N)}, $$
there exists a ...
0
votes
1
answer
68
views
Reducible/Irreducible Polynomials in Ring Theory
I have this following exercise I've been trying to solve for a while now.
We are supposed to study the irreducibility of the polynomial $A=X^4 +1$ in $\mathbb{Z}[X]$ and in $\mathbb{Z}/p \mathbb{Z}$ ...
3
votes
2
answers
188
views
Convergence of a product involving primes
Let $p_1, ... , p_n, ...$ be the prime numbers in order. Let $n \in \mathbb{N}$ and $q_1, ..., q_n \in \mathbb{N}$. Define
$$
P_n = \prod_{k=1}^n p_k^{q_k} \hspace{1cm} Q_n = \prod_{k=1}^n \left( p_k^{...
2
votes
1
answer
37
views
How to find a primitive element to split a prime $p$ in a number field
The Dedekind-Kummer Theorem allows one to split primes in a number field $K$ by splitting the minimal polynomial of $\alpha$ modulo $p$, where $\alpha$ is a primitive element for $K$ contained in the ...
0
votes
0
answers
76
views
Is the following function $f(k)$ surjective?
Let $\omega(n)$ be the number of distinct prime factors of the positive integer $n$.
For a positive integer $k$ , let $s$ be the smallest positive integer such that $\omega(2024^s+k)\ne s$ , in other ...