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
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 ...
- 17.4k
-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,...
- 275k
14
votes
3
answers
33k
views
fastest method to determine if two numbers are coprime
I am working on a mathematical problem that involves coprime integers. I wrote a computer program that allows me to search for the numbers I am looking for. However I am looking at a large set of ...
- 10.8k
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 ...
- 8,023
2
votes
1
answer
75
views
Computing the radical of an integer's equality
As stated in an answer here, there is no easy algorithm for computing the radical of an integer. My question is whether or not there is an efficient algorithm to computer whether or not the radical of ...
- 261
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 ...
- 429k
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 ...
- 141k
3
votes
4
answers
3k
views
How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$?
How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$?
Fundamental theorem of arithmetic: Each number $n\geq 2$ ...
- 275k
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
2
answers
90
views
SemiPrime Test to determine distance between P and Q
I have two composite primes (semiprimes) where $17*641 = 10897$ and $101*107 = 10807$.
Notice that $10897$ and $10807$ are almost equal. Their square roots are $104.38$ and $103.95$ respectively. But ...
- 129
4
votes
4
answers
804
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$ , ...
4
votes
1
answer
177
views
Is the "reverse" of the $33$ rd Fermat number composite?
If we write down the digits of the $33$ rd Fermat number $$F_{33}=2^{2^{33}}+1$$ in base $10$ in reverse order , the resulting number should , considering its magnitude , be composite.
But can we ...
- 305