All Questions
Tagged with prime-factorization elementary-number-theory
608
questions
2
votes
1
answer
97
views
Show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs
I am trying to show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs. I'm pretty sure this is true but I don't see how to prove it. There is no obvious way to use induction.
Here is an example:
$...
- 3,187
2
votes
1
answer
149
views
Factoring 319375146 without a calculator
The goal is to factor $N = 319375146$ without a calculator, using only pencil and paper in under 30 minutes. The exact question is "What is the 4 digit prime factor of 319375146?" This comes ...
- 5,230
2
votes
0
answers
286
views
Can factoring $90$ help factor $91$?
There are few posts asking if factoring $N-1$ can help factor $N$. In those posts the focus was on the factors of $N-1$ and $N$ which can never be the same. The conclusion therefore was that ...
- 1,058
3
votes
1
answer
217
views
A question about prime factorization of composite Mersenne numbers and $(2^p-2)/(2 \cdot p)$
Mersenne numbers are numbers of the form $2^p-1$ where $p$ is a prime number. Some of them are prime for exemple $2^5-1$ or $2^7-1$ and some of them are composite like $2^{11}-1$ or $2^{23}-1$.
I'm ...
- 141
2
votes
2
answers
262
views
Prime factors of $5^n+6^n+7^n+8^n+9^n+10^n$
I currently run an integer factoring project of the numbers of the form $$5^n+6^n+7^n+8^n+9^n+10^n$$ where $n$ is a non-negative integer.
Do the prime factors have a particular form as it is the case ...
- 85.1k
2
votes
1
answer
98
views
Is $\omega(n)=16$ the maximum?
What is the largest possible value of $\omega(n)$ (the number of distinct prime factors of $n$) , if $n$ is a $30$-digit number containing only zeros and ones in the decimal expansion.
I checked ...
- 85.1k
0
votes
0
answers
59
views
Why trial division algorithm to find the prime factors of $N$ is $O(\sqrt{N})$, even though you need to check after $\sqrt{N}$?
I have understood that to check if $N$ is prime, it is enough to check up to $\sqrt{N}$ because if it has divisor up to that point then it's composite number. However, if you want to count all the ...
- 21
0
votes
3
answers
472
views
Is this algorithm efficient as a factorization algorithm?
Let $N=8*G+3$ $->$ $N=(4*x+2)^2-(2*y-1)^2=p*q$ with $q/p < 2$
Given this system if we choose $D^2$ odd close to $8*x+4$
$->$ $(8*x+4-D^2)=W*V$ with $V$ and $W$ odd very close to each other
...
0
votes
0
answers
31
views
Form of the divisors of a number (Prime Factorization). Is this algorithm-based proof correct? [duplicate]
I am trying to proof the following result:
For a number $n$ whose prime number decomposition is $p_1^{\alpha _1} ... p_m^{\alpha _m}$. Every divisor of $n$ has the form $p_1^{\beta _1} ... p_m^{\beta ...
- 1,231
0
votes
1
answer
59
views
ways to write out a number in exponential form
Let's say that we have a number of the form $n^n$.
How many integer pairs of the form $a^b$ are equivalent to this number?
for example, let's say that $n=8$
We have $2^{24}$, $(-2)^{24}$, $4^{12}$, $(-...
- 362
0
votes
0
answers
71
views
Show for some n Fermat’s method is faster than reverse trial division
One way to find a nontrivial
divisor of n is Fermat’s factorization method:
Suppose that we have an odd number n > 1 which we know is
composite and not a perfect square.
Calculate $\lfloor \sqrt{n}...
- 254
0
votes
0
answers
57
views
Addition on a prime factorization
This question is sort of in-between a computer science question and a math question.
Let's say I'm representing a very large number as a prime factorization in order to not break the limitations of a ...
2
votes
0
answers
56
views
Maximum size of smallest prime factor that has to be expected?
Let $N$ be a positive integer near $$3^{3^{3^3}}$$ Suppose , it has no prime factor below $10^{11}$ as it is the case for $$3^{3^{3^3}}+2^{2^{2^2}}$$
The random variable $X$ denotes the number of ...
- 85.1k
2
votes
0
answers
91
views
Is there any algorithm better than trial division to factor huge numbers?
Suppose , we want to find prime factors of a huge number $N$ , say $N=3^{3^{3^3}}+2$. We can assume that we can find easily $N\mod p$ for some positive integer $p$ (as it is the case in the example) , ...
- 85.1k
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 ...
- 85.1k