For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.

learn more… | top users | synonyms (2)

0
votes
1answer
42 views

fastest algorithm for prime factorization [on hold]

I need the fastest algorithm to factorize the given number $N$ as a product of primes. $$N=p_1^{e_1}p_2{e_2}\ldots p_n^{e_n}$$ where $p_1, p_2,\ldots ,p_n$ are primes and $e_1,e_2,\ldots, e_n$ are ...
0
votes
1answer
40 views

Factorization of rational powers of rational numbers

If I am not wrong, rational powers of rational numbers can be factorized in an unique way as product of rational powers of different prime numbers: $10^{1/2} = 2^{1/2} \cdot 5^{1/2}$ $(8/9)^{1/6} = ...
1
vote
1answer
69 views

What percentage of rooms would be trapped in the cube?

In the movie Cube the design is based heavily in math. I'm trying to figure out the approximate percentage of rooms that would be trapped. His knowledge of the outer shell's size allows Leaven to ...
0
votes
1answer
24 views

Largest $k$ such that $(p-k) = \lceil \sqrt{(p-2k) p} \rceil$

Assume $p \in \mathbb P.$ Assume $0<p-2k<p$ and the next square larger than $p(p-2k)$ is $(p-k)^2$. It is trivial to show that $p(p-2k)+k^2$ is a square. Simply $p(p-2k)+k^2 = (p-k)^2.$ ...
0
votes
2answers
27 views

Divisors of the product of two coprime integers can be written as the product of two coprimes

In my lecture notes: Let $m,n\in \mathbb{N}$ be relatively prime. The fundamental theorem of arithmetic implies that each divisor of $mn$ is the product of two unique positive relatively prime ...
0
votes
1answer
21 views

Are there infinitely many real quadratic number fields with unique factorization?

Unique factorization is a commutative ring in which every non-zero non-unit element can be written as a product of prime elements (or irreducible elements), uniquely up to order and units. I'm ...
1
vote
1answer
34 views

What's the best software for primality tests of huge numbers? (check if an integer is prime or not)

I just read an article about huge prime numbers (some with more than 10millions digits!) that are discovered using software that check if an integer is prime or not (primality test sofwares). What is ...
4
votes
1answer
108 views

Lenstra's Elliptic Curve Algorithm

I am currently trying to understand Lenstra's Elliptic Curve Algorithm for factoring integers. As a source I use "Rational Points on Elliptic Curves" by Joseph H. Silverman and John Tate. They ...
0
votes
1answer
37 views

Find the height of prime ideal $p=(x_n-x_1^n,\ldots ,x_2-x_1^n)$ in $\mathbb{C}[x_1,\ldots,x_n]$

Find $\operatorname{ht}(p)$ where $p=(x_n-x_1^n,\dots,x_2-x_1^n)$ ideal of $\mathbb{C}[x_1,\ldots,x_n]$. $\operatorname{ht}(p)=$ height of a prime $p$ How to prove $p$ is prime ?
0
votes
2answers
48 views

Question regardles primes and the fundamental theorem of arithmetic

I have been reading through my book of practice proofs and came across this particular question which has stumped me. $p$ and $q$ are primes. Prove $\forall p \in \mathbb{Z}, \forall k \in ...
7
votes
5answers
665 views

Induction hypothesis misunderstanding and the fundamental theorem of arithmetic.

The fundamental theorem of arithmetic is made of two parts: The existence part: There exist primes such that for any natural number $j$, we can write $j$ as a product of prime numbers. The ...
6
votes
1answer
50 views

Lattice-Theoretic Interpretation of the Fundamental Theorem of Arithmetic

When equipping $\mathbb{N}^\ast=\mathbb{N}\setminus \{0\}$ with the divisibility relation, it forms a lattice with minimum 1, supremum given by the least common multiple, and infimum given by the ...
0
votes
0answers
31 views

Properties of previous/next natural number.

Knowing the prime factorization of a certain number $n \in \mathbb N$, what can be said about the properties of $n \pm 1$?
1
vote
2answers
25 views

Having trouble understanding phrasing.

I am having a little trouble understanding the following: "If $p_1, \ldots, p_k$ be the list of distinct primes dividing the product $mn,$ then we can factor $m$ and $n$ as $m=p_1^{r_1} \cdots ...
2
votes
1answer
92 views

True or False: For $n>1$, $n!$ can never be a perfect square.

I am trying to solve the following: True or False: For $n>1$, $n!$ can never be a perfect square. I am thinking on the following lines: Any perfect square $N$ is of the form ...
0
votes
0answers
28 views

Reasoning about factorials and powers of a finite set of primes

I am working on an answer to another question: How to prove $k!+(2k)!+\cdots+(nk)!$ has a prime divisor greater than $k!$ I've reduced the question to showing that the following infinite set of ...
0
votes
1answer
49 views

Is $512^3+675^3+720^3$ a composite number?

Q & A style A question for High school students (Calculators not allowed !): Is $512^3+675^3+720^3$ a composite number? I am posting this in Q & A style. Any suggestion will be appreciated.
3
votes
1answer
66 views

A sum regarding prime factorization

Prime factorization of $n$ is $n = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}$ Let $f(n) = \left((p_1^{a_1}+1)(p_2^{a_2}+1)(p_3^{a_3}+1)\cdots(p_k^{a_k}+1)\right)$ I want to find the value of ...
0
votes
1answer
52 views

What is the quickest and most simple way of **integer factorization by hand**?

I've searched for some algorithms but still wonder which method is best for human to calculate a not that big one such as: Calculate the factorization of 2345 and 3456 Note: Just for the examples, ...
0
votes
0answers
9 views

Quadratic Sieve: Target value in computing sum of logarithms

I've been reading Scott Contini's thesis that implements the quadratic sieve. In the MPQS, Figure 2.2 Trial Division Stage, why is the target value $\log(M\sqrt{N})$ minus a small error term? ...
2
votes
3answers
78 views

If $3$ divides $q^3$, is it true that $3$ divides $q$?

I think this is true because of prime factorisations, i.e. If $3$ a factor of the prime factorisation of $q^3$, then $3$ is a factor of the prime factorisation of $q$. Therefore If $3$ divides ...
2
votes
2answers
44 views

A fast factorization method for Mersenne numbers

Given a prime number $p$ and a Mersenne number $M=2^p-1$: Is it true for every prime factor $q$ of $M$ that $q\equiv1\pmod{p}$? For example, $p=29$ and $M=536870911=233\cdot1103\cdot2089$: $ ...
2
votes
3answers
83 views

Smallest Prime Factor - Why does this algorithm find prime numbers?

I have been looking at the problems on Project Euler and a number of them have required me to be able to find the prime factorisation of a given number. While looking for quick ways to do this, I ...
1
vote
2answers
70 views

Is it sufficient for a number to be a prime if it is not divisible by prime numbers smaller than it?

I am student of computer science with no knowledge of maths. To write a small algorithm I searched for the solution first. There are many but almost all of them state that continue dividing the number ...
2
votes
3answers
75 views

can it be proven that something is “difficult” (prime factoring for example)

I understand that the current state of the art suggests that factoring into primes is a difficult problem. I also understand that a large part of public key cryptography seems to be based on that ...
1
vote
1answer
120 views

Is my conjecture true? : Every primorial is a superior highly regular number, and every superior highly regular number is a primorial.

I have invented two sets of positive integers: highly regular numbers and superior highly regular numbers. A positive integer $m \leq n$ is a regular of the positive integer $n$ if all prime numbers ...
1
vote
1answer
85 views

How many regulars do the primorials 223092870 and 6469693230 have?

Regulars = Divisors + Semidivisors http://global.britannica.com/EBchecked/topic/496213/regular-number So for example: 6 has 5 regulars: 1, 2, 3, 4, 6. 8 has 4 regulars: 1, 2, 4, 8. 9 has 3 ...
2
votes
5answers
60 views

Understandng euclids theorem

Reading this Wikipedia article, it states "If q is not prime, then some prime factor p divides q" Why does some prime factor divide q? Does mean that for any number there is some prime factor p that ...
0
votes
1answer
63 views

Show that $b_n > b_{n-1}$ where $\frac{a_n}{b_n}$ are the n:th harmonic number

Let $H_n=\frac{a_n}{b_n}$ where $H_n$ is a n:th harmonic number and $a_n$ and $b_n$ are coprimes. 1/ If $n$ is a prime power, show that $b_n > b_{n-1}$ 2/ Find the integer factorization of ...
4
votes
5answers
298 views

Is $n^2 + n + 1$ prime for all n?

I recently stumbled across this question in a test. Paul says that "$n^2+n+1$ is prime $\forall\:n\in \mathbb{N}$". Paul is correct, because... Paul is wrong, because... The ...
1
vote
1answer
44 views

Efficient factorization of numbers with unique prime factors

I need a factorization algorithm for numbers of the form $n = p_{1}p_{2}\cdots p_{k}$ with $p_i \neq p_j$ for $i \neq j$ and $p_j \in \{p : p \mbox{ is a prime and } p \leq P_s\}$, where $P_s$ is the ...
0
votes
2answers
24 views

solving this equation using prime numbers

Solve in $\mathbb{Z}$ the following equation: $3^x$+$3^y$=$738$, using prime numbers concept and decomposition in prime factors... I noticed that the above equation is symmetrical to $x$ and $y$, ...
2
votes
1answer
19 views

how to solve this equation using certain concepts

Solve in $\mathbb{Z}$ the following equation: $x^6$ + $3x^3$ + $1$ = $y^4$, using, if it's possible, prime numbers & decomposition in prime factors concepts... Thanks for your time!
6
votes
3answers
369 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 ...
3
votes
3answers
53 views

$\operatorname{lcm}(n,m,p)\times \gcd(m,n) \times \gcd(n,p) \times \gcd(n,p)= nmp \times \gcd(n,m,p)$, solve for $n,m,p$?

$\newcommand{\lcm}{\operatorname{lcm}}$ I saw this in the first Moscow Olympiad of Mathematics (1935), the equation was : $$\lcm(n,m,p)\times \gcd(m,n) \times \gcd(n,p)^2 = nmp \times \gcd(n,m,p)$$ ...
2
votes
1answer
31 views

Proof confirmation: If $\gcd(u,v)=1$ and $uv$ is a square, then $u$ and $v$ are squares.

This is a problem from my workbook(not homework), and I can tell that it is true simply upon observation(They share no factors[other than one] and they, when multiplied have all squares as their ...
4
votes
6answers
70 views

Product of r consecutive integers is divisible by r!

Well in a book i am reading it is given that you can also prove this by showing that Every prime factor is contained in $(n+r)!$ as often at least as it is contained in $n!r!$. How does this prove ...
1
vote
1answer
32 views

Soft Question: What Does “Zero Density” mean in prime numbers?

I'm reading through an article on Paul Erdos (http://www.ams.org/notices/199801/vertesi.pdf) and on page 22 they mention the following: Calling 714 and 715 a “Ruth-Aaron pair”, we conjectured ...
1
vote
2answers
68 views

factor 9997 using quadratic reciprocity

I looked up the factorization and it is $13\cdot769$, but I have no idea how quadratic reciprocity allows you to deduce this without knowing it. I thought maybe ...
1
vote
0answers
29 views

Is there any concept similar to unique factorization that applies to exponential operators?

We can talk about prime numbers over multiplication but is there any similar concept that applies to exponential operators or other hyperpowers like tetration? Can we use what we know about UFDs to ...
1
vote
0answers
14 views

Are there unique factorizations for weyl algebras?

I just read about Weyl algebras, and they sound like neat little toys that are similar in a number of ways to polynomials. However its curious to me that they are non-commutative, and I was wondering ...
2
votes
2answers
41 views

Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer

Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer if $n$ is odd then $n=2^{0}n$, but I dont know what to do when ...
4
votes
3answers
233 views

Greatest prime factor of $4^{17}-2^{28}$

I have seen the solution to this problem. What is the greatest prime factor of $ \ 4^{17} - 2^{28} \ $? Answer: 7 $$ 4^{17}-2^{28} \ = \ 2^{34}-2^{28} \ = \ 2^{28} \ (2^6-1) \ = \ 2^{28} \ ...
2
votes
0answers
42 views

Question on Fermat Numbers Factorization

Let $F_{n}=2^{2^n}+1$ be a Fermat number. A classic idea using orders and Fermat's Little Theorem shows that a prime divisor $p$ of $F_{n}$ must be of the form $p=k .2^{n+1}+1$. Furthermore, using the ...
0
votes
0answers
19 views

Can the General Number Field Sieve be used to factor in any unique factorization domain?

Related slightly to my question about factoring in quadratic rings, can you use the general number field sieve to factor in any unique factorization domain? Can you use it in any UFD that isn't the ...
0
votes
1answer
43 views

Find the natural numbers so that n=2*a^2 ,n=3*b^3 ,n=5*c^5.Number theory problem.

Well here it is i spend almost 3 hours on this one!! Find the general form of the natural numbers that are twice a square ,tripple of a cube and 5 times a 5-ith power.Who is the smaller of them?.What ...
0
votes
0answers
14 views

Group of numbers with common euler's totient function result [duplicate]

I was asked to find the group of integers, which share the result of euler's function of 84. To be clear: which numbers, when applying eulers function on them, result 84. By calculating I found that ...
0
votes
1answer
34 views

Number Theory Prime Factor Problem

There is an integer N that has 12 factors, including 1 and itself, but only 3 of them are prime factors. The sum of these three prime factors is 20. What is the smallest possible value for N?
2
votes
1answer
76 views

How to find $\sum_{d\mid n}(w(d)w(\frac{n}{d}))$?

i) $w(n)$ is the prime divisor count function. For example $w(6)=2$ ii) Let prime factorization of $n=p_{1}^{a_{1}}p_{2}^{a_{2}}.....p_{w(n)}^{a_{w(n)}}$ iii) Lets define this function. ...
1
vote
1answer
93 views

Is $(1+2+3+…)=(1+2+2^2+2^3+…)(1+3+3^2+…)(1+5+5^2+…)…$?

Are these equal? $$(1+2+3+…)=(1+2+2^2+…)(1+3+3^2+…)(1+5+5^2+…)…$$ Where the RHS has a series for each prime. Looks like they are the same series by the fundamental theorem of arithmetic. Every number ...