Questions tagged [prime-factorization]
For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.
1,989
questions
0
votes
0
answers
12
views
Have numbers of this form forced small factors?
Let $F_n$ be the $n$ th Fibonacci-number and define $$f(n):=F_{n^2}-F_n+1$$
For most integers $n>1$ , $f(n)$ has a small prime factor :
...
- 81.1k
0
votes
0
answers
13
views
$n$ odd composite number, at most $\frac{n-1}{4}$ integers $a$ such that $n$ is a strong pseudoprime with respect to $a$
The problem I'm trying to solve is:
Let $n$ be an odd composite number. Show there are at most $\frac{n-1}{4}$ integers $a$ such that $1 \leq a \leq n$ and $n$ is a strong pseudoprime with respect to $...
- 35
0
votes
1
answer
118
views
How to factor numbers like 8,023 manually
I was given a random 4-digit number to factor over the prime numbers. My number was 8,023. I tried applying all the divisibility rules up to 36 before giving up on them. I tried using algebra as ...
- 1,957
1
vote
1
answer
44
views
How would one show that any given prime p_i must be a factor of some (p_j - 1)? Is that a true property of primes even? [closed]
In short, what I'm asking is, if you were to go through the whole set of positive primes term by term and find for each prime p the prime factorization of (p - 1), whether all prime numbers would ...
- 19
0
votes
1
answer
43
views
Calculating factorization for large numbers
My mission is to calculate the factorization of large numbers, for example, from $start=1e11$ to $end=1e12$.
To do that, one approach that I was thinking of is to calculate for each number his ...
-1
votes
2
answers
61
views
Prime and Integer Factorization
Often in problems I find myself having a hard time factoring really large or "complex" numbers.
How am I supposed to know that $43,911$ is $41 * 63 *17$ ?
Are there any methods or tricks or ...
- 39
0
votes
0
answers
64
views
Efficient algorithm for finding the number within an interval given its prime factors
Suppose we are given two integers $\ell$ and $h$ such that $\ell \leq h$ and a list of distinct prime numbers $P = [p_1,p_2,\dots,p_n]$ (sorted in ascending order). We are interested in finding an ...
- 191
0
votes
0
answers
57
views
Question about the collection of the prime factors of a fibonacci number
A positive integer $n$ is called pandigital , if every digit from $0$ to $9$ occurs in the decimal expansion of $n$.
Conjecture : The largest non-pandigital fibonacci-number (a fibonacci-number with ...
- 81.1k
0
votes
0
answers
87
views
Prime divisors of $f(n):=F_{n^2}+F_n+1$?
Let $F_n$ be the $n$ th fibonacci-number and define $$f(n):=F_{n^2}+F_n+1$$
For which positive integers $n$ do we have no small prime factor (say $p<10^7$) $p\mid f(n)$ ? Are there useful ...
- 81.1k
1
vote
1
answer
88
views
Finding the (smallest) next number with the same distinct prime factors as a previous number
(Since there is no answer yet, I removed most "EDIT"'s to make the text more readable)
Today, I was trying to find a natural number $n_{2}$ such that this number has the same distinct prime ...
2
votes
0
answers
61
views
What are nontrivial factors of $F_{F_n}$ upto $n=137$?
Let $F_n$ denote the $n$ th Fibonacci number and define $f(n):=F_{F_n}$
$f(n)$ is prime for $n=4,5,7$
If we have $n>4$ and $F_n$ is composite , then we only have to know a prime factor of $F_n$ , ...
- 81.1k
-2
votes
1
answer
102
views
A number theory problem I saw, related to prime factors [closed]
Prove that there are infinitely many prime factors of numbers of the form $2^{3^k}+1$.
- 181
0
votes
0
answers
22
views
Clarification on Exponents in Prime Factorization of Ideals in Dedekind Domains and Number Fields
Let $R$ be a Dedekind domain and $I$ a proper ideal. Then I know $I$ can be expressed uniquely as a finite product of prime ideals:
$$
I = \prod_{\mathfrak{p} \text{ prime}} \mathfrak{p}^{n_{\mathfrak{...
- 567
1
vote
1
answer
66
views
Legendre's Conjecture and estimating the minimum count of least prime factors in a range of consecutive integers
I recently asked a question on MathOverflow that got me thinking about Legendre's Conjecture.
Consider a range of consecutive integers defined by $R(x+1,x+n) = x+1, x+2, x+3, \dots, x+n$ with $C(x+1,x+...
- 10.3k
0
votes
0
answers
45
views
What is the name of a number that does not have repeating prime factor
For example, $10$ does not have repeating prime factor, $2$ and $5$, while $20$ have repeating prime factor, $2 \cdot 2 \cdot 5$. What is the name of number that does not have repeating prime factor? ...
- 103
2
votes
2
answers
98
views
The equation $175a + 11ab + bc = abc$ [closed]
Consider all the triples $(a, b, c)$ of prime numbers that satisfy the equation
$$175a + 11ab + bc = abc\ .$$
Compute the sum of all possible values of $c$ in such triples.
I could only get to the ...
- 33
0
votes
0
answers
27
views
About the proof of reduction of factoring to order finding
Inside the book I'm following there's a theorem, used to prove the factoring algorithm, which states:
Suppose $N = p_{1}^{\alpha_1}p_{2}^{\alpha_2}\dots p_{m}^{\alpha_m}$ is the prime factorization of ...
0
votes
2
answers
66
views
Method to finding the number of factors [duplicate]
I've seen that the number of factors of $x$ can be found:
Prime factorising $x$
Taking each power in the factorisation and adding $1$
Multiplying these numbers together.
This results in the number ...
- 593
3
votes
2
answers
128
views
Is there an efficient algorithm for generating all numbers with n distinct prime factors in order?
Bit of an x y problem here, so in full disclosure, I am attempting to find the next term of A152617, "Smallest number m such that m has exactly n distinct prime factors and sigma(m) has exactly n ...
- 215
1
vote
1
answer
73
views
Prove that $\sqrt{-5}$ is a prime in the ring $R=ℤ[\sqrt{-5}]$.
If $R=ℤ[\sqrt{-5}]$ is a ring but not a UFD, prove that the irreducible element $\sqrt{-5}$ is a prime.
This is what I have so far.
Proof: Let $R=ℤ[\sqrt{-5}]$ be a ring but not a UFD. Since $\sqrt{-5}...
1
vote
2
answers
72
views
Sum of co-primes of a number $n \le k$
Problem
Given a number $n$ and a number $k$ ($k\leq n$) we are to find
sum of co-primes of $n$ less than or equal to $k$
My thoughts
factorise $n$
and then do $k(k + 1)/2$ - ...
- 460
1
vote
1
answer
75
views
Solution of $\sigma(\sigma(m)+m)=2\sigma(m)$ with $\omega(m)>8$?
This question is related to this one.
$\sigma(n)$ is the divisor-sum function (the sum of the positive divisors of $n$) and $\omega(n)$ is the number of distinct prime factors of $n$.
The object is ...
- 81.1k
0
votes
0
answers
36
views
Pollard's rho factorization turns out slower than trial division?
Learning basic number theory, I wrote a simple program to factorise integers by trial division. The next task was to learn and implement Pollard rho algorithm (hopefully, order(s) of magnitude faster ...
1
vote
0
answers
104
views
Is $n=2$ the only even solution of $\sigma(\sigma(n)+n)=2\sigma(n)$?
Inspired by this
question.
For positive integer $m$ , let $\sigma(m)$ be the divisor-sum function.
Let $S$ be the set of positive integers $n$ satisfying $$\sigma(\sigma(n)+n)=2\sigma(n)$$ In the ...
- 81.1k
0
votes
1
answer
45
views
Difference in two products of prime factorizations
Let $\Phi(n)=\{p_1, p_2, ..., p_k\}$ be the set of prime factors of a number $n$. How does
$$
p_1(n) = \prod_{p_i\in\Phi(n) \\ 1 \le i \le k}{p_i}
$$
compare to
$$
p_2(n) = \prod_{p_i\in\Phi(n) \\ 1 \...
- 100
1
vote
1
answer
61
views
Given a partial prime factorization of $N$ consisting of all primes $p \leq \sqrt{N}$ that divide $N$, how do I find the rest of the factorization?
Given an integer $N$, let $P$ be the set of all primes less than or equal to $\sqrt{N}$ that divide $N$. Define $P_{prod}$ as $\prod_{p \in P} f_N(p)$ where $f_N(p) \gt 1$ is the largest power of $p$ ...
- 1,417
5
votes
2
answers
255
views
Number of maximal antichains in the set $\{1,2,3,4,5,6,...,120\}$ where the order is by divisibility relation.
Find the number of maximal antichains in the set $\{1,2,3,4,5,6,7,...,120\}$ where the order is divisibility relation. For example, $\{6,7,15\}$ is an antichain but not a maximal antichain, and $\{1\}$...
- 3,147
0
votes
1
answer
51
views
Two combinatorics questions, one on product of combinations, the other on why factoring heuristic isn't applicable
In a group of $14$ students, there are $8$ girls and $6$ boys. Determine the number of ways that a committee of $4$ students which has at least $1$ boy can be chosen from the group.
Why is the answer ...
user1152896
-1
votes
1
answer
39
views
Finding common modulo
given these two modulo equations $c_1 = m_1^a (\mod n)$, $c_2 = m_2^a (\mod n)$
Where '$a$' is prime and $n$ is a product of two primes, and the only unknown is $n$, is it possible to solve for $n$? I ...
- 9
0
votes
1
answer
32
views
In an $AKLB$ setup, does norm of an integral element being in a prime ideal of $A$ imply that the element is in a prime ideal of $B$ lying above?
Suppose that $A$ is a Dedekind domain with field of fractions $K$. Let $L$ be a finite separable extension of $K$, and $B$ be the integral closure of $A$ in $L$. We know that $B$ is also a Dedekind ...
- 955
8
votes
2
answers
141
views
Showing that prime factors of a number is congruent to $1 \pmod 5$
I have come across numbers of the form
$$b=1+10a+50a^2+125a^3+125a^4$$
where $a$ is a positive integer.
Looking at the prime factors of $b$, I am conjecturing that all prime factors of $b$ are $\equiv ...
- 1,056
1
vote
1
answer
52
views
Set of natural numbers related to least common multiple
I have come across the following set in my research, and I am curious whether this has been studied before/if there is a reference for a related construction.
Given a natural number $n$, let $S(n)$ be ...
- 1,186
2
votes
0
answers
40
views
Quadratic Sieve on the Gaussian Integers
Factoring a large Gaussian integer $z_0 = a+bi$ into Gaussian primes may be done by first factoring the norm $N(z_0) = a^2 + b^2$ over the integers, and then considering the factors of each integer ...
- 775
0
votes
0
answers
76
views
No. of ways of factorizing a number into three distinct factors
Question: Let m be the number of triplets (p,q,r) of positive integer such that
p<q<r and pqr is the square of the product of primes between 2 to 19
(including), when m is divided by 100 what ...
1
vote
0
answers
74
views
Are the Poulet-numbers of the form $k^2+1$ all squarefree?
A Poulet-number $n$ is a weak Fermat-pseudoprime to base $2$ , in other words a composite number $n$ with the property $$2^{n-1}\equiv 1\mod n$$
The first $34$ poulet-numbers of the form $k^2+1$ (...
- 81.1k
0
votes
0
answers
47
views
Find upper and/or lower bounds for the least prime $p$ such that $p^n + k$ is the product of $n$ distinct primes
Well, first of all, happy new year to everyone.
I am trying to solve the following problem: "Let $k$ be a fixed natural number. Find the least prime $p$ such that there exists a natural number $...
- 28.3k
4
votes
0
answers
97
views
Valid Elementary Proof of the Bertrand-Chebyshev Theorem/Bertrand's Postulate? [closed]
$\textbf{Theorem}$ (Bertrand-Chebyshev theorem/Bertrand's postulate): For all integers $n\geq 2$, there exists an odd prime number $p\geq 3$ satisfying $n<p<2n$.
$\textit{Proof }$: For $n=2$, we ...
- 395
2
votes
1
answer
231
views
Largest known positive integer n such that $\binom{n}{k}$ has k prime factors (counted with multiplicity) for each $k\le32$
The numbers n such that $\binom{n}{1}$ have $1$ prime factor (counted with multiplicity) are simply the primes. Therefore, for $k=1$ this gives the largest known prime, $n=2^{82589933}-1$. For $k=2$, ...
user1115547
1
vote
1
answer
48
views
Lets that $p_1,p_2, ...,p_\lambda>2$ be a set of prime numbers. Is there estimation for the summation of $ A=\sum_{i=1}^{\lambda}\varphi(p_i-1)$?
Lets that $p_1,p_2, ...,p_\lambda>2$ be a set of primes number greater than $2$. Is there any exact formula or estimation for the summation
$$
A=\sum_{i=1}^{\lambda}\varphi(p_i-1)
$$
- 755
-1
votes
1
answer
64
views
Suppose a, b are integers and LCM(a, b) = GCD(a, b)^2. What can be said about the prime decompositions of a and b? [duplicate]
Unsure how to approach the problem besides using the fact that the LCM(a,b) * GCD(a,b) = a*b. I see the implication that the GCD(a,b)^3 = a * b. Perhaps it means a and b are different powers of the ...
- 1
2
votes
1
answer
61
views
How to solve $x^x \equiv 0 \pmod y$
Given a constant y, I am trying to find the smallest value for x that satisfies the equation $x^x = 0 \mod y$. So far I have been able to determine that $x$ is equal to the product of all the prime ...
- 21
3
votes
1
answer
116
views
Numbers between powers of consecutive primes
So if we try to categorize numbers based on the number of their prime factors we would have something as following where $L_n$ is the list of numbers with $n$ prime factors.
$$
L_1 : 2, 3, 5, 7, 11, .....
- 367
0
votes
0
answers
68
views
Are there any pairs of integers that are divisible by the same primes such that adding $1$ or $2$ also keeps them divisible by the same primes?
The answer to this question shows that there are infinitely many pairs of integers $(m, n)$ such that $m$ and $n$ have the same prime factors, and $m+1$ and $n+1$ also have the same prime factors. Are ...
- 3,777
4
votes
3
answers
136
views
Non-squarefree numbers of the form $10^n + 1$
Consider numbers of the form $10^k + 1$. We can look at the prime factorisation of these numbers and note that the smallest such number that has a repeated prime factor is $10^{11} + 1 = 11^2\cdot{}23\...
- 335
1
vote
1
answer
149
views
Are there finitely many pairs of integers that are divisible by the same primes such that adding $1$ also keeps them divisible by the same primes? [duplicate]
Integers m and n have the same prime divisors but m is not equal to n, i.e. the same primes are just raised by different powers, resulting in integers m and n. But we also know that m+1 and n+1 have ...
3
votes
2
answers
598
views
A proof that every integer greater than 1 is a product of primes
In my calculus textbook we are asked to prove that every integer greater than 1 is a product of primes. This theorem is not new to me, however, the proof they provide seems unnecessarily long.
Proof: ...
user1124791
3
votes
1
answer
115
views
Length of this representation increases really slowly?
$$\def\'{\text{'}}\def\len{\operatorname{len}}$$
A recent Code Golf challenge introduced a "base neutral numbering system". Here I present a slightly modified version, but the idea is the ...
- 460
-1
votes
2
answers
64
views
Why does Euclid theorem fail in some cases? [duplicate]
The euclidean theorem says that if we have a limited prime numbers and we added 1 it cant be divided by any prime numbers
I notice that it work in some cases with lower number but when I added a ...
- 111
0
votes
1
answer
66
views
Formula for finding the prime structure of a number [duplicate]
Consider a positive integer $N$, it can be written in form of prime numbers as;
$$N=2^{a_{2}}3^{a_{3}}5^{a_{5}}....p_{i}^{a_{i}}$$
Thus that number $2520$, for instance,can be written as:
$$2520=2^{3}...
1
vote
0
answers
50
views
Is there a certain pattern with the prime factorization of numbers adjacent to each other.
So, recently, I was playing around with random numbers and their prime factorizations in my free time. Basically, what I would do, was take a number, say x.
I would take the prime factorization of x, ...
