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
3
votes
1
answer
303
views
Interesting pattern that I found while finding dice that always roll a prime number
The original puzzle I was trying to solve is to find unique numbers to write on the faces of two dice such that the numbers you see on each dice after rolling sum to a prime.
I realized that for this ...
- 353
1
vote
1
answer
1k
views
Prime and Factorization, prime divisor property
Let $p$ be prime. Then if $p|ab$ then $p|a$ or $p|b$.
Proof:
Suppose $p$ does not divide $a$
Then $\gcd (a,p) = 1$ since $p$ is prime.
$$ 1 = ma + np $$
$$ b = mab +npb$$
Since $p|map$ and $p|npb$...
- 151
0
votes
2
answers
90
views
Factorization of Primes and Greatest Common Divisors
If $a=q_1^{e_1}q_2^{e_2}...q_r^{e_r}$ and $b=s_1^{f_1}s_2^{f_2},...s_u^{f_u}$ are the factorizations of $a$ and $b$ into primes, then there exist primes $t_1<t_2<...<t_v$ and nonnegative ...
- 1,557
4
votes
3
answers
393
views
If $a \mid c$ and $b \mid c$, but $\gcd(a,b) = 1$, then $ab \mid c$.
If $a | c$ and $b | c$ and $a$ and $b$ are relatively prime prove that
$ab|c$.
What I did was since $(a,b)=1$ then we can find integers $m,n$ such that $ma + nb=1$. Now since $a|c$ then $a = mc$. ...
- 1,089
0
votes
1
answer
1k
views
Sum of number of factors of first N numbers [duplicate]
Given a number N ( Value can be large like N < 10^9 ) How can we calculate sum of the number of factors of first N numbers??
Example :
For n = 3
Answer:
= #f(1) + #f(2) + #f(3) --- { #f(n) ->...
- 21
5
votes
2
answers
288
views
Why does prime factorization hold in the set of integers of the form $4k+1$?
I want to prove that in the set
$$ S = \{4k+1 : k\text{ is a positive integer}\}$$
(i.e. $S = \{1, 5, 9, 16, \dots \}$) unique prime factorization holds. How do I do that?
Edit: a prime in this ...
- 51
2
votes
2
answers
954
views
Factoring 1001 in $\Bbb Z[\sqrt 7]$
I am solving the problem of factoring 1001 into prime elements in $\Bbb Z[\sqrt 7]$.
I have a couple of questions regarding this.
It seems that $\Bbb Z[\sqrt 7]$ is an Euclidean domain. But I do ...
- 7,290
1
vote
2
answers
70
views
Is this factorization correct?
I have this problem:
$$\sqrt[3]{8x^5}-\sqrt[3]{27x^8}$$
The result I get is:
$$x\sqrt[3]{x^2}(2-3x)$$
But I don't know if I factored it correctly because the answer is:
$$\sqrt[3]{x^2}(2x-3x^2) $$
- 283
4
votes
1
answer
2k
views
How can I find decompositions in $\mathbb{Z}[\sqrt{d}]$?
Decompositions in $\mathbb{Z}$
In $\mathbb{Z}$ you can find a decomposition of any element $n \in \mathbb{Z}$ by factorization such that
$$n = \prod_{p \in \mathbb{P}} p^{v_p(n)}$$
So for a ...
- 9,891
0
votes
1
answer
80
views
There is an ambiguity in wording that I do not understand for a factor problem.
The problem is as follows
If $A = 9n$ and $B = 8n$ where $n$ is a positive integer, which one has a greater number of distinct prime factors ?
According to the answer, we cannot tell.
However, I ...
- 5,175
0
votes
1
answer
49
views
Finding $n$ such that $\sum^{n}_{k=0} \frac{2}{p_k} = \left ( \prod^{n}_{j=0} p_j^{-1}\right) p_x$
Let $p_n$ denote the $n$th prime.
Is it possible to find $n$ such that
$$\sum^{n}_{k=0} \frac{2}{p_k} = \left ( \prod^{n}_{j=0} p_j^{-1}\right) p_x$$
any other way than calculating both the ...
- 2,089
2
votes
2
answers
2k
views
Algorithm to determine if a number is a product of consecutive primes
I want to implement a program in C++ with which I can see if a number $n$ has a prime factorization of only consecutive primes.
For example $30=2\cdot 3 \cdot 5$ is such a number, while $21=3 \cdot ...
- 2,632
8
votes
3
answers
2k
views
Finding the sum of two numbers knowing only the primes
Pretend $N_1$ is the prime factorization of 30 and $N_2$ is the prime factorization of 8. Is there a way, using only $N_1$ and $N_2$, to get the prime factorization of the sum, 38?
It is easy to do ...
- 918
2
votes
1
answer
98
views
Fermat's Method - Derive worst case $n=3p$
I am currently trying to understand Fermat's method: for a number $n$ we start with $x=\lceil\sqrt{n}\rceil$ and check if $\sqrt{x^2-n}\in\mathbb N$, if not, increase $x$ and try again, etc. until $x^...
- 23
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 ...
- 2,624