Questions tagged [prime-factorization]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
47 views

What could be the possible multiple of $x$ in the equation $12x = 5y^2$

If $x$ and $y$ are integers and $12x = 5y^2$, What could be the possible multiples of $x$ ? What can we infer about $y$ ? I have approached this problem like this : \begin{align} x = \dfrac{5y^2}{12}...
user avatar
  • 19
5 votes
2 answers
152 views

Periodic sequences of integers generated by $a_{n+1}=\operatorname{rad}(a_{n})+\operatorname{rad}(a_{n-1})$

Let's define the radical of the positive integer $n$ as $$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\ p\text{ prime}}}p$$ and consider the following Fibonacci-like sequence $$a_{n+1}=\...
user avatar
3 votes
0 answers
109 views

Smallest squarefree number with $\varphi(n)\mid \sigma(n)$ and smallest prime factor $p$

Let $\ p\ge 5\ $ be a prime number. How can I efficiently find the smallest squarefree number $\ n\ $ with $\ \varphi(n)\mid \sigma(n)\ $ having $\ p\ $ as the smallest prime factor , where $\sigma(n)...
user avatar
  • 78.4k
-2 votes
1 answer
44 views

What do you call rings that have unique factorizations?

For example, integers, gaussian integers, and polynomials all have unique factorizations. What are these rings (or this property) referred to as? Or is unique factorization a ubiquitous property that ...
user avatar
  • 1,612
2 votes
0 answers
19 views

Maximum number of distinct primes in a defined product

The following question grows out of my thinking about the distribution of primes and twin primes. I could provide a lot of background as to how I arrived at this question, but that background isn't ...
user avatar
0 votes
1 answer
54 views

how to find the smallest number with exactly n distinct *prime* divisors [closed]

I saw a question where it was just asking for the smallest number with n distinct divisors, but I'm looking for n distinct prime divisors. For example, the prime factorization of 8 is 2 * 2 * 2, so it ...
user avatar
0 votes
1 answer
48 views

Find two prime factors of a number so that the multiplication of factors give the original number

I have a number say N, I need to divide this number into p and q so that when I multiply p and q I would get original number back. Also, p and q should be two prime numbers. Google search suggest to ...
user avatar
  • 179
-2 votes
0 answers
53 views

Can any positive integer (arbitrary) be the prefix for some prime number? [duplicate]

Suppose we have an integer $n$. Then, construct a prime integer $m (> n)$, such that $m - (m \mod 10^k) = n \cdot 10^k$ for some $k$.
user avatar
2 votes
0 answers
71 views

Are there infinite many primes $\ p\ $ that cannot divide $\ 3^n+5^n+7^n\ $?

Let $\ M\ $ be the set of the prime numbers $\ p\ $ such that $\ p\nmid 3^n+5^n+7^n\ $ for every positive integer $\ n\ $ , in short the set of the prime numbers that cannot divide $\ 3^n+5^n+7^n\ $. ...
user avatar
  • 78.4k
20 votes
3 answers
624 views

Is $\frac{3^n+5^n+7^n}{15}$ only prime if $n$ is prime?

Let $f(n)=3^n+5^n+7^n$ It is easy to show that $\ 15\mid f(n)\ $ if and only if $\ n\ $ is odd. I searched for prime numbers of the form $g(n):=\frac{3^n+5^n+7^n}{15}$ with odd $n$ and found the ...
user avatar
  • 78.4k
1 vote
1 answer
44 views

Adequately defining the fundamental theorem of arithmetic.

Adequately defining the fundamental theorem of arithmetic. So after sifting through the internet, I realized that there are a few ways the fundamental theorem of arithmetic is defined. Paraphrasing, ...
user avatar
3 votes
0 answers
86 views

Does the following hold as a conjecture for maximum gaps between prime numbers? and can it be proved?

Even though I used matrix related mathjax on the backend, the frontend is intended to be just a regular table. $$\begin{matrix} a&X&X:explanation \\1&1 \\2&3 \\3&5 \\4&(6)&(...
user avatar
  • 1,365
2 votes
0 answers
52 views

Largest possible prime factor for given $k$?

Let $k$ be a positive integer. What is the largest possible prime factor of a squarefree positive integer $\ n\ $ with $\ \omega(n)=k\ $ (That is, it has exactly $\ k\ $ prime factors) satisfying the ...
user avatar
  • 78.4k
-1 votes
2 answers
66 views

How to understand special prime factorization method

Normally when we want to find the Prime Factorization of a number, we will keep dividing that number by the smallest prime number (2), until it can't be divided then we move on to the next prime ...
user avatar
1 vote
1 answer
49 views

Numbers for Testing Integer Factoring Algorithms

I'm looking for a list of numbers with which to test an integer factorization algorithm (for a computer). Something that has numbers harder than the ones I could easily come up with. Do any resources ...
user avatar
1 vote
1 answer
59 views

contest problem: number theory, prime factorization, perfect squares

Problem Statement: Gretchen labels each of the six faces of a cube with a distinct positive integer so that for each vertex of the cube, the product of the three numbers on the faces touching the ...
user avatar
1 vote
1 answer
40 views

Proof of uniqueness of prime factorization by induction with Euclid's Lemma [duplicate]

The uniqueness of the prime factorization is proved here on Wikipedia. I am wondering whether the initial trick could be extended to a full proof without using contradiction as it's done there. So, ...
user avatar
1 vote
0 answers
80 views

Can I make use of the "high" exponents here?

I currently try to factor the composite number $$3^{130}+5^{130}+7^{130}$$ and wonder whether the quadratic sieve can be accelerated because of the "high" exponents. I know that for numbers ...
user avatar
  • 78.4k
3 votes
1 answer
71 views

Is there any way to find a row of numbers with many prime factors?

According to the Erdos–Kac theorem, $\sigma=\frac{\omega(n)-\log\log n}{\sqrt{\log\log n}}$ is close to the standard normal distribution, where $\omega(n)$ is the number of distinct prime factors on $...
user avatar
  • 1,193
4 votes
1 answer
61 views

Is there a comprehensive list of complexity theoretic reductions from and to prime number factorization?

I am interested in the complexity theoretic equivalences of prime number factorization. I am especially interested to learn wether there are some not initially obvious reductions. Im sure there is a ...
user avatar
  • 237
3 votes
1 answer
66 views

Is the number of ways to express a number as sum of two coprime squares same as number of solution of $x^2+1\equiv0\pmod n$

The number of representations of $n$ by sum of 2 squares is known as sum of square function $r_2 (n)$. It is known that if prime factorization of $n$ is given as $$2^{a_0}p_1^{a_1}p_2^{a_2}\cdots q_1^{...
user avatar
  • 3,505
7 votes
2 answers
1k views

Is there any variation known to the sum of two squares theorem?

Originally posed by Fermat and subsequently generalized as sum of two squares theorem, we can see the following statement. An integer greater than one can be written as a sum of two squares if and ...
user avatar
  • 331
1 vote
0 answers
41 views

Let $\mathbb{Z}[i]$ denote the *Gaussian integers*. Factor both $3+i$ and its norm into primes in $\mathbb{Z}[i]$

Question: Let $\mathbb{Z}[i]$ denote the Gaussian integers. (a) Compute the norm $N(3+i)$ of $3+i$ in $\mathbb{Z}[i]$ (b) Factor both $3+i$ and its norm into primes in $\mathbb{Z}[i]$ (c) Compute $\...
user avatar
  • 1,151
1 vote
0 answers
71 views

What are the integers that lack unique factorization in $\mathbb Z[\zeta_n],$ $n= 23$? [closed]

In the cyclotomic integers $\mathbb{Z}[\zeta_n]$, $n=23$ has class number $3$ and so unique factorization fails (https://en.wikipedia.org/wiki/Cyclotomic_field ). Can anyone give me examples of such ...
user avatar
1 vote
1 answer
44 views

Notation for the number of $n$'s in $x$'s prime factorization

$f_n(x)$ is equal to number of $n$'s in $x$'s prime factorization. Or, put differently: $$x = \prod_{i=1}^mp_i^{e_i}, \quad f_{p_i}(x) = e_i$$ I'd like to know if there is notation for this, so that I ...
user avatar
0 votes
0 answers
22 views

Is there an efficient method to perform additions on prime factorization objects?

Lets say I have an ordered list of primes P = [2,3,5,7...] and 2 vectors f1 and f2 such that the numerical value of f1 or f2 is computed as the product of each prime to a corresponding power in the ...
user avatar
  • 85
1 vote
4 answers
82 views

Show that there are infinitely many functions $f:\mathbb N\rightarrow\mathbb N$ satisfying $f(2)=2$ and$f(mn)=f(m)f(n) \forall m,n\in \mathbb N$

Show that there are infinitely many functions $f:\mathbb N \rightarrow \mathbb N$ such that (a) $f(2)=2$ (b) $f(mn)=f(m)f(n)$ for all $m,n\in \mathbb N$$ Solution as in book: Here we use another ...
user avatar
  • 1,563
1 vote
2 answers
102 views

Using Least Common Multiple to find the number of rectangle pieces of a given size to fit a square surface

I would be grateful if someone could help me with this question. I have calculated the answer to be 24 but the answer in the book says 12. DANCE FLOORS A dance floor is to be made from rectangular ...
user avatar
0 votes
1 answer
35 views

pattern in max number of distinct prime factors of any number in [1,n]

While solving a math-based programming problem, I had to write a function to compute the maximum number of distinct prime factors for any number in the range $[1, n]$ for any number $n$. I tested this ...
user avatar
0 votes
0 answers
40 views

How can we find small primes $\ p\ $ with $\ \omega(p^2-1)=n\ $ efficiently?

Inspired by this question , I define $\ p(n)\ $ to be the smallest prime $\ p\ $ such that $\ \omega(p^2-1)=n\ $ (assuming such a prime exists) , where $\ n\ $ is a positive integer. If we can show ...
user avatar
  • 78.4k
0 votes
0 answers
25 views

What is the asymptotic behavior of the number of $\varepsilon$-primes?

Let $\varepsilon \in (0,\frac{1}{2})$ be a fixed parameter and define a positive integer $n$ to be $\varepsilon$-prime if it has no divisors in the range $[n^\varepsilon, n^{1-\varepsilon}]$. Consider ...
user avatar
  • 2,793
0 votes
1 answer
67 views

Let a rational number $\frac{a}{b}$ in its lowest form where $a$,$b$ are integers, with $0 < \frac{a}{b}< 1$, b > 1. How many of these have $ab = 15!$

Consider a rational number $\frac{a}{b}$ in its lowest form where $a$, $b$ are integers, with $0 < \frac{a}{b}< 1$, b > 1. How many of these have $ab = 15!$ Solution Given in Book: $15!=2^{11}...
user avatar
  • 1,563
2 votes
0 answers
152 views

Sequences of consecutive "fair" positive integers

Ok so here is a question I thought of (while trying to solve some numbers inequalities of course): Definition: We will call a number $n$ "fair" if for all $p$ prime numbers such that $v_p(n)=...
user avatar
1 vote
1 answer
39 views

Bounds on prime factors of minors of an integer matrix

Let's say we are given a matrix $M$ with integer entries, i.e. $M\in \mathrm{Mat}_{n\times m}(\mathbb{Z})$. For some reason, we are interested in determining the rank of this matrix over arbitrary ...
user avatar
  • 190
0 votes
3 answers
128 views

Is it practical to find actual very large prime numbers (such as those up to 100 digits)? [closed]

I just asked How to find extremely large BigInt prime numbers exactly in JavaScript? and was explained that all I ever can hope for is a "probable" prime, not an exact/actual prime if they ...
user avatar
  • 3,156
3 votes
2 answers
303 views

Definition of UFD and the fact that UFDs are integrally closed

I am trying to understand the proof of the fact that UFDs are integrally closed. In addition to the lecture notes I have, there are at least two solutions on MSE: One is here: How to prove that UFD ...
user avatar
19 votes
2 answers
509 views

$\lim_{n \to \infty}\frac{1}{n}\sum_{k = 1}^nf(k)$ where $f(n)$ is the largest prime factor exponent?

Let $f(n)$ the be largest exponent among exponents of the prime factor of $n$. E.g. $f(80) = 4$ since $80 = 2^4.5$ and the prime factor of $80$ which has the largest exponent is $2$ which occurs with ...
user avatar
-1 votes
2 answers
73 views

Factoring- Pre Algebra Homework question

I'm studying pre-algebra with an App called Brilliant. I'm in a lesson called "Factoring Sums with Variables". I got most of the exercises right, but there's one that I don't understand. To ...
user avatar
  • 101
3 votes
2 answers
121 views

Shouldn't the definition of a prime number be changed to account for negative factors?

At the moment, from what I can gather the current definition of a Prime Number is; "a number that is divisible only by itself and $1$ (e.g. $2, 3, 5, 7, 11$)". However such a prime number ...
user avatar
1 vote
3 answers
164 views

Are primes only defined for a specific set?

When we are talking about primes, are they defined only in terms of the set/structure they belong to? E.g. $3$ is a prime but $3= (\sqrt 7 - 2)(\sqrt 7 + 2)$ so it has factors but since they do not ...
user avatar
  • 1,507
5 votes
1 answer
100 views

Values of the Liouville function

Let $\Omega: \mathbb{N} \to \mathbb{N}\cup\{0\}$ be the function which counts how many prime factors a number has, with multiplicity. For example, $\Omega(380) = 4$, $\Omega(108)= 5$. More generally, ...
user avatar
2 votes
1 answer
103 views

Unique factorisation theorem for $\mathbb{Z} \setminus \{0\}$

The unique factorisation theorem for positive integers states that every positive integer can be uniquely expressed as a product of primes. What does "uniqueness" mean here? Let $n\in \...
user avatar
  • 4,395
1 vote
1 answer
40 views

Use Fermat-Kraitchik’s factorization to factor $85026567$

I have to use Fermat-Kraitchik’s factorization to factor $n=85026567$. I already know that $85026567$ is divisible by $3$, and therefore $85026567=3\cdot 28342189$, and both of the factors are prime. ...
user avatar
  • 1,323
6 votes
1 answer
172 views

Finding the prime factors of $2^{14}+3^{14}$ by hand

I need to find the prime factors of $2^{14}+3^{14}$ by hand (this was given in an exam at my university, so this is the motivation - I decided to state this because it may look unjustified to try to ...
user avatar
0 votes
1 answer
63 views

An example showing $\mathbb{Z}[\sqrt[3]{7}]$ is not a UFD [closed]

It cannot be a UFD because it's the ring of integers of $\mathbb{Q}(\sqrt[3]{7})$ and has class number 3. How can we give an example showing this?
user avatar
  • 55
2 votes
1 answer
51 views

Sum of Prime Factorizations and Primes

If I partition an integer and get the prime factorization of each partition, is there a way to tell if my original integer was a prime? For example, given the factorization of my partitions $$71 = (56)...
user avatar
-1 votes
1 answer
99 views

Properties of $F(p)=p^2+1$, where $p$ is a prime number

Let $F(p)=p^2+1$, where $p$ is a prime number. For what primes $p_1$, $p_2$ does $p_2$ divide $F(p_1)$ and $p_1$ divide $F(p_2)$? Two examples are $\{p_1,p_2\}=\{5,13\}$, and $\{p_1,p_2\} = \{89,233\}...
user avatar
2 votes
2 answers
53 views

Prove that if $k\mid q_1...q_n$ then we can find $k_i$ such that $k=k_1...k_n$ and for every $i$, $k_i\mid q_i$

Let $k=8$ and $q_1=12$, $q_2=2, q_3=5$. We note that $k\mid q_1q_2q_3$, but $k\nmid q_1$ and $k\nmid q_2$ and $k\nmid q_3$. Also $$ 8=k_1k_2k_3=4*2*1, $$ where $k_1\mid q_1$, $k_2\mid q_2$, and $k_3\...
user avatar
0 votes
0 answers
32 views

Factorization of Polynomials over $\Bbb Z_p$ using GAP

I want to factorize Polynomials using GAP. Here is an example: ...
user avatar
0 votes
1 answer
37 views

how to denote a number that could be divisible by A but not B, both A and B are large integers

The age numbers of four people are a sequence of natural numbers. The oldest person in these four people is not older than 30. The product of four ages number is divisible by 2700, but not 81. How ...
user avatar
  • 299

1
2 3 4 5
38