Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [prime-factorization]

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

A natural number is prime if it has no positive divisors besides $1$ and itself. The fundamental theorem of arithmetic states that every natural number $n>1$ can be factored uniquely, up to a reordering of the factors, as a product of distinct prime numbers each raised to some power.

This concept holds in a more general setting though. A ring is called a unique factorization domain (UFD) if every non-unit element can be factored uniquely as a product of prime elements in the ring. The ring of integers is an example of a UFD.

2072 questions
10
votes
4 answers

Negative factors of a number

Can a factor of a number be negative? Is $-5$ a factor of $25$ or $-25$? A number is said to be prime if it has two factors : $1$ and the number itself. So if $-5$ can be a factor of $5$, how to define the prime numbers? Thanks.
ammar
  • 297
7
votes
2 answers

Decompose Number with Prime Factor

Given a number n, Here are two operations can be taken: n - 1 n divide by its prime factor Question: In order to decompose n to 1, what is the minimal operations should be taken? For example, in term of number 29, it is a prime number. So, the…
unknown
  • 89
6
votes
3 answers

Smallest Prime-Factor of $4^{52} + 52^{2013} + 2013^{52}$

I would like to find out the smallest prime factor of $4^{52} + 52^{2013} + 2013^{52}$ by hand. Thanks in advance
Prankster
  • 567
  • 4
  • 15
6
votes
5 answers

How do they check really large primes?

Currently, the largest prime know is a mersenne, $2^{82,589,933} − 1$. That’s an $82,589,933$-bit number if I am correct. Considering that RSA codes of as low as 1024 bits can be considered safe, how was this number factored to check if it is prime?…
shell bertt
  • 69
6
votes
0 answers

Is there a pattern for the distribution of prime factor count for numbers under n?

In the below picture I have charted the distribution of numbers below n by factor count. The bottom line is for all numbers under 100,000 then 200,000 ... all the way to 1,000,000. They seem to tend to a specific set of numbers. Right now I am…
Joe
  • 534
5
votes
3 answers

Prime factorization number theory

Let $n$ be a positive integer, and let $ 1=d_1
user255231
4
votes
3 answers

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} \ \cdot \ 63 \ = \ 2^{28}\ \cdot \ 3^2 \ \cdot \ 7 $$ I…
Hagz
  • 41
4
votes
1 answer

Prime factorization of

For a positive integer $k$, let $S_k$ be the set of numbers $n > 1$ that are expressible as $n = kx + 1$ for some positive integer $x$. The set $S_k $ is closed under multiplication. That is: If $a, b$ ∈$ S_k $then $ab $∈ $S_k$. Definition. Suppose…
Kai
  • 89
4
votes
1 answer

Factorizing integers on cluster of computers?

Maybe this is more of a CS question (or even crypto) than a mathematical one but here we go. Lets say I want to factorize a huge number $n$ (the likes used for RSA) but I don't have the computational requirements to do so. However I have an army of…
Adam
  • 686
4
votes
0 answers

How to compare numbers by prime factorizations?

Let's say I have two natural numbers $n$ and $m$, both of which are exceeding large, and I want to determine which is smaller. Thankfully, I happen to know both of their prime factorizations, but they're composed of many terms to high powers, so…
InsertCreativityHere
  • 83
4
votes
1 answer

Find prime factorization of $2^{22} + 1$

Find the prime factorization of $2^{22} + 1$. How can I approach this with a subtle way? I know that $a^n -b^n = (a-b) (a^{n-1}+a^{n-2}b + \cdots + ab^{n-2}+b^{n-1})$ and $a^{2n+1} + b^{2n+1} = (a+b) (a^{2n}-a^{2n-1}b + \cdots - ab^{2n-1}+b^{2n})$.…
Gary
  • 271
3
votes
0 answers

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? Shouldn't the target value depend on $x$? I'm worried…
user448810
  • 577
3
votes
1 answer

On prime factors of composite integers

I have a question on prime factors of composite integers. It is known that for any composite integer N, N must contain a prime factor $p$ $\leqslant$ $\sqrt n$. I then thought of the following question: Suppose N $\leqslant$ $x$ $\leqslant$ N + 3,…
user86111
  • 363
3
votes
3 answers

Factorize: $x^3 + x + 2$.

How do I factorize the term $x^3 + x +2$? What I have previously tried is the middle term factor method but it didn't work... $x^3 + x + 2$ $\Rightarrow x^3 + 2x - x + 2$ $\Rightarrow x(x^2 + x) - 2(x - 1)$ This doesn't work. What should I do?
Suparno Saha
  • 43
3
votes
2 answers

Is there a function to eliminate repetitive factors?

Say I have a number, like 60. Which has a prime factorization of $$[2,2,3,5]$$ What function would take in 60 and remove redundant factors? In this case, it should return 30 Edit: I did some more research, and the term I'm wording in looking for is…
user406613
1
2 3 4 5 6 7