Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit 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.

0
votes
1answer
27 views

Suppose a prime number $p$ divides the product $a_1 a_2 … a_n \in \mathbb{Z} $ then $p$ divides at least one of the factors of $a_i$

I know i need to use induction but i really have no concept on how to go about it. Base case: Let $p$ divide $a_1$ then p will be a factor of $a_1$??? Inductive step: No idea how to phrase this.
0
votes
1answer
41 views

Find X in the Equation

Im not a mathematician and I have forgotten about some basics in mathematics. I have this equation: (x^y) mod z = w Given y, z and w, how will I find x? How ...
2
votes
1answer
46 views

Basics of Quadratic Sieve algorithm

I'm trying to understand Quadratic Sieve algorithm for integer factorization, I follow the description in the book "Prime Numbers" by Crandall and Pomerance, specifically the Algorithm 6.1.1. (Even ...
2
votes
1answer
25 views

Stage 1 of Elliptic Curve Method (ECM)

Reading several texts of ECM (e.g. 20 years of ECM) the Stage 1 is described as: $Q \leftarrow P_0$ for each prime $\pi <= B_1$ $\quad$compute $k$ such that $\pi^k <= B_1 < \pi^{k+1}$ $\quad$...
1
vote
1answer
101 views

Given $\varphi (n)$ and $n$ for large values, can we know prime factors of $n$

If a number is product of two primes, then given its totient function, we can know its prime factors, but how do we do this in generic case? If the number could have more than two prime factors can ...
3
votes
0answers
46 views

Factorising a divisor of a product

In the ring of integers (or the monoid of natural numbers under multiplication), I believe that the following theorem holds: Lemma Set $m$, $a$, $b$. If $m | ab$ then there exist $u$, $v$ such that $...
2
votes
1answer
51 views

Semiprime factorization

I was thinking about semiprime factorization, and I had an idea of an algorithm: Let's take a small semiprime for this example: 3053. So we have to primes ...
0
votes
0answers
23 views

Prime factorization formalism

I was hoping someone might know the name for this representation of the positive integers. The idea is similar to Peano's arithmetic but applied to multiplication. So we have 1, multiplication and a ...
-1
votes
0answers
14 views

Integer Factorization with Specific Pattern

Given a pattern vector $\vec{v}=(e_1,\cdots,e_k)$ whose elements are positive integers (not necessarily distinct), I'd like to ask how many ways to write $N!$ as $\prod_{i=1}^{k} {b_i}^{e_i}$ where $...
2
votes
0answers
33 views

How many set of size $m$ integers such that the product is $n$

just a small combinatoric question related to optimizing the amount of computations of a program (for some reasons). How many sets of $m$ naturals can be formed such that their product equals the ...
1
vote
0answers
29 views

Fermat Kraitchik Factorization Method

I am struggling to understand the following passage from my number theory book, i'm not sure i like his choice of language however it is the only book i can get a copy of for now. That being said I ...
0
votes
0answers
53 views

Finding the smallest prime factor of $\sum_{a=1}^N a^{k}$

It is linked to my previous question, but I wanted a ++ clear explanation: Suppose we have a huge number of that type with a huge $k$. $\sum_{a=1}^N a^{k} =1^{k}+2^{k}+3^{k}+...+N^{k}$ And we want ...
0
votes
1answer
63 views

Find the smallest positive prime divisor of …

Problem: That's a problem I have found on the web. I didn't understand the solution: Why?? Given solution: How all this sequence has been transformed into $$33-{\lfloor {33\over p}\...
5
votes
2answers
76 views

What is the multiplicative order of a product of two integers $\mod n$?

Standard texts prove that $\textrm{ord}_n(ab)=\textrm{ord}_n(a)\,\textrm{ord}_n(b)$ when $\textrm{gcd}(\textrm{ord}_n(a),\textrm{ord}_n(b))=1$. What if they are not relatively prime? Here $\textrm{...
10
votes
1answer
159 views

Prime divisors of the sequence terms $a_n=a\cdot 2017^n+b\cdot 2016^n$

I am dealing with the test of the OBM (Brasilian Math Olimpyad), University level, 2017, phase 2. As I've said at another topic (question 1), I hope someone can help me to discuss this test. The ...
3
votes
2answers
30 views

Find the prime factorisation of $6500$ and $1120$, and write down, in factorised form, $\gcd(6500, 1120)$ and $\operatorname{lcm}(6500, 1120)$.

(i) Find the prime factorisation of $6500$, and of $1120$. What is the typical way to go about this? Just using common divisibility rules? That's what I did. I'm not sure if there's a more structured ...
3
votes
1answer
46 views

Why a certain integral domain is not a UFD.

Let $$\mathbb{Z}[q]^{\mathbb{N}} = \varprojlim_j \mathbb{Z}[q]/((1-q)\cdots (1- q^j))$$ Why isn't $\mathbb{Z}[q]^{\mathbb{N}}$ a unique factorization domain? The author proposes a proof whose ...
1
vote
1answer
65 views

Product of a known prime

Lets say we have a set of numbers k = [44, 3, 17, 10, 64] and a known prime number p=11. How do I filter all the numbers from ...
8
votes
4answers
105 views

Determining Whether the Number $11111$ is Prime. Used Divisibility Tests.

I am asked to determine whether the number $11111$ is prime. Upon using the divisibility tests for the numbers 1 to 11, I couldn't find anything that divides it, so I assumed that it is prime. However,...
0
votes
0answers
36 views

Find the cardinality of the set $A_p$ defined as the following : [duplicate]

For any prime number $p$, $A_p$=the set of integers $d\in \{1,2,3,\dots, n\}$ such that the power of $p$ in the prime factorization of $d$ is odd. Then \begin{align*} A_p= & \lfloor\dfrac{n}{p}\...
1
vote
1answer
28 views

finding the number of positive divisors for a 1111…1 1992 times

So the actual question is to prove that the number of positive divisors is even. But to do that I have to find the number of positive divisors for 111.....1(1992 1's). I know that I should try to find ...
3
votes
1answer
106 views

Find the largest of the three prime divisors of the number $13^4 + 16^5 - 172^2$

I was able to factor out only the prime 13,thus $13^4 + 16^5 - 172^2=13\cdot 80581$ What should be done to solve it? (Maybe some clever factorization, modulo, or anything else?)
2
votes
3answers
77 views

If $S(n)$ is an odd integer, what is the sum of all possible $\frac1n?$ [closed]

If $n$ is a positive integer, let $S(n)$ be the sum of all the positive divisors of $n$. If $S(n)$ is an odd integer, what is the sum of all possible $\frac1n?$ The function $S$ is multiplicative ...
3
votes
0answers
55 views

Binary eigenvalues matrices and continued fractions

I'm working on a rational approximation of the square root function by continued fractions in the complex plane. The following kind binomial coefficients Hurwitz matrices (for $n=4$ and $6$) play ...
1
vote
1answer
74 views

Concise way to accurately find factors of any number?

The last number of $365$ is $5$, therefore I’ve been told that $5$ is a factor of $365$, which it clearly is. This however does not work for other numbers, i.e., $9$ is not a factor of $8599$. I’ve ...
1
vote
3answers
53 views

Find the number of trailing zeros in 50! [duplicate]

My attempt: 50! = 50 * 49 *48 .... Even * even = even number Even * odd = even number odd * odd = odd number 25 evens and 25 odds Atleast 26 of the numbers will lead to an even ...
0
votes
1answer
146 views

probability of prime factor

Question, what are the chances for obtaining the same, prime factor 55049? The SUM of List A gives a factor of 17 x 55049 and the sum of list B gives a factor of 19 x 55049 I want to understand how ...
4
votes
5answers
167 views

A simple method of factorization $ 2^{30}+1 $

How can you factor $ 2^{30} + 1 $? This task was supposed to be at one interview, there is an assumption that there should be a simple solution.
0
votes
1answer
55 views

Understanding part of derivation of Chebychev's Theorem

I cannot understand this result from pages 17–18 of Tenenbaum and Mendes's The Prime Numbers and Their Distribution on how the summation of $\frac{x\log(2)}{2^j}+O(\log(x))$ results in $2x \log(2) + O(...
-3
votes
1answer
69 views

Probability of attaining same prime factor [closed]

EDITED: Two coloums of numbers are presented, there are 234 entries in both columns. Column A, values are not multiples of 19, natural numbers increasing by a random value with mean of 30. Column B, ...
4
votes
2answers
155 views

A Proof of the Fundamental Theorem of Arithmetic

Is there a proof of the Fundamental Theorem of Arithemetic that does not make use of the Integers or Rational Numbers (as opposed to using only the Natural Numbers)? And if so, what is it? By the ...
2
votes
2answers
81 views

How to calculate the number of possible multiset partitions into N disjoint sets?

I have made a Ruby program, which enumerates the possible multiset partitions, into a given number of disjoint sets (N), also called bins. The bins are indistinguishable. They can be sorted in any ...
0
votes
0answers
21 views

Quality of prime seeking methods

I am working on prime numbers with emphasis of prime search heuristics, and found the probabilistic methods for primes seeking, I am looking for a review of those methods quality in terms of machine ...
1
vote
0answers
55 views

Plotting the sum of prime factors of integers with rational exponents [closed]

In a sense, some numbers other than integers can be written in terms of prime factors. For example $$ \sqrt[3]{\frac{1}{6^{5}}} = 6^{\frac{-5}{3}} = 2^{\frac{-5}{3}} \times 3^{\frac{-5}{3}} $$ We ...
0
votes
2answers
115 views

Does this qualify as a prime-representing Diophantine equation?

Given the below coefficients, if the Diophantine equation $Axy + Bx + Cy + D = \lfloor\frac{n}{3}\rfloor$ has exactly one solution, then $n$ is prime, otherwise $n$ is composite. In a sense, this ...
1
vote
1answer
56 views

Every integer greater than $0$ can be expressed as a sum of $a$'s and $b$'s, if and only if $a$ and $b$ have no common factor

Every integer greater than $0$ can be expressed as a sum of $a$'s and $b$'s, if and only if $a$ and $b$ have no common factor. PROOF: Consider the case $a=5$, $b=13$. First, let's find how to ...
-1
votes
1answer
46 views

An algorithm to reduce a factorisation problem into an easier one?

Question I recently wondered about my own factorisation method (see method) to generate a smaller number to factorise than the original one. What are some "good methods" to choose $\lambda$ and $\...
1
vote
1answer
36 views

Show that prime polynomial is irreducablr [closed]

Let p be a prime number. Question is for any prime value of p the polynomial $$1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...++\frac{x^p}{p!}$$ is irreducable. I found out that it seems like a ...
6
votes
2answers
175 views

How were the factors of $\frac{521^{521}-1}{520}$ found?

In factordb, I came across this factorization : CF 1413 (show) (521^521-1)/520<1413> = 8794442339...49<706> · 6489962533...29<707> How ...
0
votes
0answers
35 views

Factorization of $(q^q - (-1)^{(q-1)/2})/(q-(-1)^{(q-1)/2})$

Prove that for any prime $q > 3$, $(q^q - (-1)^{(q-1)/2})/(q-(-1)^{(q-1)/2})$ is never prime (or disprove by counterexample). If this is true, is there a possible trivial factorization for $(q^q - ...
3
votes
2answers
51 views

Proving $5S= \langle 5,{\alpha} +2\rangle\,\langle 5, {\alpha}^2+3{\alpha}-1\rangle$

I need help in verifying the following equality: $$ 5S = \langle 5, \alpha +2\rangle\, \langle 5, {\alpha}^2+ 3 \alpha -1\rangle $$ where $S= \mathbb{Z}[{2}^{1/3}]$ and $\alpha = 2^{1/3}$. It seems ...
0
votes
1answer
19 views

If $n^2$ is a multiple of an even-exponent prime factorization, then is $n$ a multiple of the square root of the given prime factorization

Inspired by an excerpt from pp. 209 of ETS's Official GRE Prep Guide (2017): Since every value of $n^2$ is a multiple of $(2^4)(3^4)$, the values of $n$ are the positive multiples of $36$. ...
1
vote
1answer
41 views

Word to describe factor of x or 1/x

There is a well known video of a helicopter with 5 evenly spaced rotor blades where the rotor is synced with a digital camera's frame rate. Assuming the camera is at 60 hertz (60 frames per second), ...
2
votes
1answer
112 views

The equation $\varphi(n)=n-\log_2(1+\operatorname{gpf}(n))-\operatorname{gpf}(n)+1$ and Mersenne primes

Let $n\geq 1$ an integer, we denote the Euler's totient function as $\varphi(n)$ and the greatest prime dividing $n$ as $\operatorname{gpf}(n)$ (that it the arithmetic function defined in the ...
2
votes
1answer
44 views

Are there infinitely many primes of the form $2\,m^{\operatorname{gpf}(m)}+1$ when $m$ runs over positive integers?

Let $n\geq 1$ an integer, in this post we denote the greatest prime dividing $n$ as $\operatorname{gpf}(n)$. See it you want the article from MathWorld Greatest Prime Factor. While I was writing ...
0
votes
2answers
132 views

An inequality involving the radical of an integer and its greatest prime factor

Let $n\geq 1$ an integer, in this post I denote the greatest prime dividing $n$ as $\operatorname{gpf}(n)$, and the product of the distinct prime numbers dividing $n$ as $$\operatorname{rad}(n)=\prod_{...
-2
votes
1answer
49 views

On an inequality involving the radical of an integer and its greatest prime factor

Let $n\geq 1$ an integer, in this post I denote the greatest prime dividing $n$ as $\operatorname{gpf}(n)$, and the product of the distinct prime numbers dividing $n$ as $$\operatorname{rad}(n)=\prod_{...
2
votes
1answer
48 views

Concatenation of Prime Factors in Base-m : Conjecture about Divisibility

As per suggestion, this is being posted as a separate question Given the prime-factor concatenation of n in base-m (I'll use the notation $ PFC_m(n) $), if n is a composite number ($c_k$), does $\...
1
vote
1answer
33 views

Product of unique prime factors of a number

Given $n=p^x q^y r^z$ (with p, q, and r prime), is there a name for the number $m = p q r $ or the function f(n) = m? Eg., For $n = 52 = 2*2*13$, $m = 2*13 = 26$ For $n = 3300 = 2*2*3*5*5*11$, $m = 2*...
2
votes
1answer
21 views

Number of prime elements in a ring

Is there any way to count the prime elements in a ring? More precisely a way to count prime elements in a UFD? Which would be the same as counting irreducibles. Are there even UFD with finitely many ...