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
4
votes
4
answers
812
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
178
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
1
vote
1
answer
101
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 ...
- 275k
1
vote
1
answer
64
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 ...
- 126k
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
0
votes
1
answer
69
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}$ ...
- 67.8k
10
votes
1
answer
1k
views
When is $(p-2)!-1$ power of $p$ if $p$ is prime?
If $p$ is prime, for what values of $p$ is $(p-2)!-1$ a power of $p$? I know how to solve that when $p<5$ then $(p-1)!+1$ can be written as power of $p$.
- 21
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 ...
- 47.8k
3
votes
2
answers
191
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^{...
- 82.2k
6
votes
2
answers
678
views
Prove $a^3\mid b^2 \Rightarrow a\mid b$
I think it's true, because I can't see counterexamples.
Here's a proof that I am not sure of:
Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$
\begin{eqnarray}
a&=& p_1^{\...
- 275k
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
6
votes
1
answer
867
views
A problem related to the factors of $(2^n+1)$ [duplicate]
Here's the conjecture:
For $n\in\mathbb{N}^*$, $(2^n+1)$ always has a prime factor with form $(2nk+1)$ where $k\in\mathbb{N}^*$, with an exception when $n=3$.
For example, when $n=5$, we have $2^5+1=...
- 449
2
votes
4
answers
320
views
Counting Divisors Proof
How can be proved that the number of positive divisors is equal to:$$
(e_{1}+1)(e_{2}+1)....(e_{n}+1)
\
$$
where $e_{i}$ is the ith exponent of the prime factorization.
- 54.3k
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 ...
- 2,792
3
votes
1
answer
90
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 ?
...
- 2,792
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 "$...
- 275k
1
vote
2
answers
1k
views
Finding Prime Factors of a number in $\log(n)$
Only Strategy I am aware of for finding factors efficiently is sieve of eratosthenes but from sieve I first have to pre-compute the prime numbers less than than $\sqrt{n}$. I want to skip this ...
- 32.3k
35
votes
3
answers
17k
views
What are examples of irreducible but not prime elements?
I am looking for a ring element which is irreducible but not prime.
So necessarily the ring can't be a PID. My idea was to consider $R=K[x,y]$ and $x+y\in R$.
This is irreducible because in any ...
- 13.1k
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,249
3
votes
2
answers
223
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 ...
- 3,337
0
votes
2
answers
523
views
In Pollard p-1 how is the bound B chosen?
Does Pollard's p-1 method always produce an answer (given sufficient time and assuming input is composite)? If yes, what is the point of having the bound $B$, why not just keep increasing $a$? If no, ...
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 ...
- 61.5k
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,190
26
votes
1
answer
536
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 ...
- 4,401
1
vote
1
answer
202
views
Resource to implement Block Lanczos in python;.
I am trying to implement GNFS in python and I wanted to make it as fast as possible just because. I am trying to find a resource that will help me implement Block Lanczos but so far haven't seen many ...
0
votes
1
answer
56
views
Working out prime factors
I am having issues working out questions similiar to the below. I understand the general concept, but is there something I am missing to be easily about to see that the prime factors of 899 are 23 and ...
- 101
0
votes
0
answers
39
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
10
votes
5
answers
796
views
Find all the prime factors of $1000027$
Find all the prime factors of $1000027$.
I got all the factors by testing every number from $1$ to $103$, but when I try to do it using algebra, I get stuck.
My work:
$$
1000027=(100+3)(100^2-3\...
- 1,788
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 ...
- 2,638
9
votes
6
answers
1k
views
Smallest known unfactored composite number?
I'm trying to find examples of "small" numbers which are known to be composite, but for which no prime factors are known. According to this website the number $109!+1$ is a composite number of 177 ...
- 349
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
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.7k
2
votes
1
answer
44
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
0
votes
1
answer
34
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)$ ...
- 239k