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,...
- 37
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 ...
- 85.1k
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,647
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 ...
- 1,789
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 ...
- 153
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&...
- 11
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 ...
- 83
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}$ ...
- 11
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^{...
- 1,289
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 ...
- 2,058
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 ...
- 85.1k
1
vote
1
answer
55
views
Prove that the set of positive rational numbers is countable
While I was studying Discrete Mathematics, I faced a question that I do not understand how to solve even after looking at the answer. The question asks me to prove that the set of positive rational ...
- 145
0
votes
0
answers
13
views
What is the rate of increase in magnitude of a sorted list of factors of a large integer
I understand that the Hardy-Ramanujan theorum shows that a very large integer $n$ will on average have about $log(log(n))$ distinct factors. What I am interested in is how the magitude of the factors ...
- 1,204
1
vote
1
answer
56
views
Distribution of perfect numbers for a semiprime
Given a semiprime with a length of 120 digits (397bit):
is it possible to meet any assumptions about perfect numbers (prime factors with same length, 199+199bit) for this number?
I have made an ...
- 121
2
votes
2
answers
97
views
How to describe integers with the same prime factors?
Is there a term for the relationship between two integers that have the same prime factors? For example, $6=(2)(3)$ and $12=(2)(2)(3)$. Can one describe this with something along the lines of "$...
- 23
3
votes
2
answers
219
views
Two questions around some new card game based on prime factorization.
I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...
- 699
6
votes
0
answers
100
views
Factorizations not sharing digits with original number
The sequence A371862 is "Positive integers that can be written as the product of two or more other integers, none of which uses any of the digits in the number itself."
In the extended ...
- 21.4k
0
votes
2
answers
65
views
prime factorization in $\mathbb{Z}[i]$ [duplicate]
We were asked to show where the following reasoning goes wrong. Since $1+i$ and $1-i$ are prime elements in $\mathbb{Z}[i]$, the equation $$(-i)(1+i)^2=(1+i)(1-i)=2$$ show that unique prime ...
- 103
4
votes
0
answers
99
views
Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$
As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
- 1,180
26
votes
1
answer
531
views
Prime factor wanted of the huge number $\sum_{j=1}^{10} j!^{j!}$
What is the smallest prime factor of $$\sum_{j=1}^{10} j!^{j!}$$ ?
Trial :
This number has $23\ 804\ 069$ digits , so if it were prime it would be a record prime. I do not think however that this ...
- 85.1k
0
votes
0
answers
38
views
Approximating a rational number in a subset of Q defined by limited prime factors
I'm wondering if there is an efficient (or good enough for small numbers) algorithm for the following problem:
Suppose I have a rational number in the form of its prime factorization:
$k = p_0^{x_0}...
- 9
3
votes
1
answer
58
views
Divisibility of numbers in intervals of the form $[kn,(k+1)n]$ [duplicate]
I have checked that the following conjecture seems to be true:
There exists no interval of the form $[kn, (k+1)n]$ where each of the integers of the interval is divisible by at least one of the ...
- 1,180
0
votes
0
answers
41
views
Question about sum of indices of prime factorisation of consecutive numbers that might be solved via Chinese remainder theorem? [duplicate]
Consider a set of (not necessarily consecutive) prime numbers, $S: = \{ p_1, p_2, \ldots, p_k\}.\ $ For each integer $n,$ for each $1\leq j \leq k,$ let (the function) $u_n(p_j)$ be the greatest ...
- 20.6k
2
votes
1
answer
41
views
Factorizaton in an Euclidean ring
I have a doubt concerning Lemma 3.7.4 from Topics in Algebra by I. N. Herstein.
The statement of the Lemma is:
Let $R$ be a Euclidean ring. Then every element in $R$ is either a unit in $R$ or can be ...
- 185
1
vote
1
answer
80
views
Understanding the upper bound implications of $R(p,n) \le \log_p n$ in the context of Wikipedia's proof of Bertrand's Postulate
In Wikipedia's proof of Bertrand's Postulate, in the second lemma, it is concluded that:
$$R = R(p,{{2n}\choose{n}}) \le \log_p 2n$$
where $R(p,n)$ is the p-adic order of ${2n}\choose{n}$
Later in the ...
- 10.5k
0
votes
1
answer
32
views
Understanding an application of Legendre's Formula as used in the proof of Bertrand's Postulate
In Wikipedia's proof of Bertrand's Postulate, Legendre's Formula is used to establish an upper bound to the p-adic valuation of ${2n}\choose{n}$
The argument is presented as this:
(1) Let $R(p, x)$ ...
- 10.5k