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
4
votes
3
answers
340
views
Show that $a^k + 1$ is not always prime when $k$ is a power of $2$
Let $a, k \geq 2$.
If $a^k + 1$ is a prime, conclude that $k$ is a power of $2$. Show that the converse is not true.
The hint is: if $n$ is odd, then $x^n + 1$ has a factor of $x + 1$.
Please help, ...
- 275k
2
votes
2
answers
63
views
Is there a more efficient way to find the least prime factor?
Assuming $Q_{k} \equiv p_{k}\text{#} + 1$, my goal is to find the least prime factor of $Q_{k}$ for each integer $k = 1 \ldots 100$ . The Python program shown below tries using SymPy to do so, but ...
- 5,239
1
vote
1
answer
158
views
Find sum of factorials divisible by the largest possible prime squared
Let $n$ be a positive integer.
Consider the following maximization problem :
Use each of the factorials $1,2,3!,\cdots ,n!$ at most once such that the resulting sum is divisible by $p^2$ , where $p$ ...
- 17.4k
3
votes
1
answer
199
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
-1
votes
0
answers
32
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.9k
1
vote
1
answer
58
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,010
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
45
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 ...
- 432k
1
vote
2
answers
73
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
27
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
92
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 ...
- 137