All Questions
Tagged with prime-factorization elementary-number-theory
608
questions
-1
votes
2
answers
111
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 ...
- 109
2
votes
0
answers
173
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 ...
- 85.1k
1
vote
1
answer
104
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 ...
user1114342
2
votes
0
answers
101
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$ , ...
- 85.1k
-2
votes
1
answer
109
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$.
- 476
1
vote
1
answer
77
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.5k
3
votes
2
answers
275
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 ...
- 270
1
vote
2
answers
95
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$ - ...
- 470
1
vote
1
answer
87
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 ...
- 85.1k
0
votes
0
answers
265
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
119
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 ...
- 85.1k
1
vote
1
answer
92
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,497
-1
votes
1
answer
46
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
8
votes
2
answers
223
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,106
1
vote
1
answer
61
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,261