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)

3
votes
2answers
47 views

Automorphisms of $\langle \mathbb{N}, \cdot \rangle$

It is an elementary fact that multiplication in $\mathbb{N}$ is commutative: $$(\forall n,m)\ n \cdot m = m \cdot n$$ This - among other things - implies that the representation of an $n \in ...
0
votes
0answers
24 views

Does a number have to be factored completely to determine if it's smooth?

For example, the number $6000$ - does it have to be completely factored to determine if it is 5-smooth? Or is there a shortcut without finding all the prime factors?
1
vote
1answer
40 views

A better way to prime factorize a set of numbers?

Let's say I have a range of numbers starting from 1 to 10^9 and I need to prime factorize each one of them.My basic algorithm is: 1.Use prime-sieve algorithms(Atkins or Eratosthenes(segmented ...
6
votes
3answers
92 views

Find the prime-power decomposition of 999999999999

I'm working on an elementary number theory book for fun and I have come across the following problem: Find the prime-power decomposition of 999,999,999,999 (Note that $101 \mid 1000001$.). Other ...
0
votes
1answer
36 views

How many distinct lists of 14 integers $L=\{v_1,\ldots ,v_{14}\}$ exist satisfying $v_i \geq v_{i+1}\geq 0$ and $\sum _{i=1}^{14}(v_i) \leq 54$

I am trying to solve the following problem: I have an ordered list of integers $L = \{v_1,\ldots ,v_{14}\}$ with fourteen elements, satisfying the following two conditions: $v_i \geq v_{i+1}\geq 0$ ...
1
vote
1answer
42 views

Divisibility problem ($p \leq \sqrt{n}$)

If $n \geq 2$ and $n$ is composite, then there exists a prime $p$ such that that $p \mid n$ and $p \leq \sqrt{n}$ As $n$ is composite, it follows that $n = ab$ for some $a, b \in \Bbb N$, where ...
0
votes
1answer
68 views

Graph theory / vertex-set list representation

If I were to consider a graph with vertex-set V= {1, 2, 3, ... 10} with the edges taken as all the pairs {x, y} of distinct members of V that have a prime factor in common, how would one write the ...
3
votes
1answer
65 views

Given the prime factorization of $n$, is it possible to know anything about the prime factorization of $n+1$? [duplicate]

I think the title is quite clear. Given $$ n = \prod_{i=1}^n p_i ^{k_i}$$ is it possible to know something about the prime factorization of $n+1$? (I mean in terms of $p_i, k_i$)
2
votes
2answers
39 views

Proof: no fractions that can't be written in lowest term with Well Ordering Principle

My question is the exact same question as the one in this post but I commented on it but it's from a year ago so I just wanted to bump it and see if I could get a response: Prove that there's no ...
1
vote
1answer
38 views

terminology for “a number with at least two distinct prime factors”

Is there an established terminology for "a number with at least two distinct prime factors"? These are the composite numbers 6 (2x3), 10 (2x5), 12 (2x2x3), 14 (2x7), 15 (3x5), ..., but not 4 (2x2), 8 ...
0
votes
1answer
153 views

Let $x = 2441921$. Factor $x$ into a product of primes.

Let $x = 2441921$. Factor $x$ into a product of primes. I found that: $1519^2 −x=−134560= −2^5 ·5 · 29^2$ and $1541^2 −x=−67240= −2^3 · 5 · 41^2$. I am trying to figure out what to do from here. ...
1
vote
0answers
43 views

How to find factors when factoring

I'm going to be a TA in an introductory course in matematics at a technical university this fall, focusing on mathematics that the students should already be familiar with but that might need ...
0
votes
1answer
45 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
72 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
27 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
28 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
24 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
41 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
112 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
50 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
680 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
52 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
34 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
26 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
95 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
31 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
51 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
72 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
53 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
10 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
79 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
48 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
103 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
76 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
81 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
127 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
64 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
301 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
46 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
25 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
387 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
32 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
75 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
34 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 ...