# Questions tagged [prime-factorization]

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

2,072 questions
Filter by
Sorted by
Tagged with
55 views

### Prime factors of ${2024}\choose{1012}$ [closed]

Given question is to prime factorise ${2024 \choose 1012}$ into prime factors of $2,5,7.$ I tried to find an alternate meaning of ${2024 \choose 1012}$ in terms of choosing $1012$ people from $2024$ ...
1 vote
52 views

### Prove that the set of positive rational numbers is countable

While I was studying Discrete Mathematics, I faced a question that I do not understand how to solve even after looking at the answer. The question asks me to prove that the set of positive rational ...
• 145
11 views

### What is the rate of increase in magnitude of a sorted list of factors of a large integer

I understand that the Hardy-Ramanujan theorum shows that a very large integer $n$ will on average have about $log(log(n))$ distinct factors. What I am interested in is how the magitude of the factors ...
• 1,189
1 vote
45 views

### Distribution of perfect numbers for a semiprime

Given a semiprime with a length of 120 digits (397bit): is it possible to meet any assumptions about perfect numbers (prime factors with same length, 199+199bit) for this number? I have made an ...
• 121
91 views

57 views

### Divisibility of numbers in intervals of the form $[kn,(k+1)n]$ [duplicate]

I have checked that the following conjecture seems to be true: There exists no interval of the form $[kn, (k+1)n]$ where each of the integers of the interval is divisible by at least one of the ...
• 1,110
40 views

### Question about sum of indices of prime factorisation of consecutive numbers that might be solved via Chinese remainder theorem? [duplicate]

Consider a set of (not necessarily consecutive) prime numbers, $S: = \{ p_1, p_2, \ldots, p_k\}.\$ For each integer $n,$ for each $1\leq j \leq k,$ let (the function) $u_n(p_j)$ be the greatest ...
• 20.4k
38 views

### Factorizaton in an Euclidean ring

I have a doubt concerning Lemma 3.7.4 from Topics in Algebra by I. N. Herstein. The statement of the Lemma is: Let $R$ be a Euclidean ring. Then every element in $R$ is either a unit in $R$ or can be ...
• 175
1 vote
79 views

### Understanding the upper bound implications of $R(p,n) \le \log_p n$ in the context of Wikipedia's proof of Bertrand's Postulate

In Wikipedia's proof of Bertrand's Postulate, in the second lemma, it is concluded that: $$R = R(p,{{2n}\choose{n}}) \le \log_p 2n$$ where $R(p,n)$ is the p-adic order of ${2n}\choose{n}$ Later in the ...
• 10.4k
30 views

### Understanding an application of Legendre's Formula as used in the proof of Bertrand's Postulate

In Wikipedia's proof of Bertrand's Postulate, Legendre's Formula is used to establish an upper bound to the p-adic valuation of ${2n}\choose{n}$ The argument is presented as this: (1) Let $R(p, x)$ ...
• 10.4k
1 vote
145 views

### Minimum $k$ for which every positive integer of the interval $(kn,(k+1)n)$ is composite

I am looking for references containing results on the minimum $k$ for which every positive integer of the interval $(kn,(k+1)n)$ is composite. If we denote as $k(n)$ this minimum $k$ for some $n$, $k$ ...
• 1,110
41 views

### Existence of prime elements in an atomic integral domain

Let $R$ be an integral domain, is it true that if $R$ is atomic, then it must contain a prime element? If not, what is a counterexample? I know that if an element is prime, then if $I$ is the ideal ...
• 43
36 views

### Denjoy's Probabilistic Interpretation

Does Denjoy's Probabilistic Interpretation actually "prove" that the Mertens function ratio between numbers with odd number of distinct prime factors and even number of prime factors is 1? ...
• 37
1 vote
66 views

### Prime Divisor of the Sum of Two Squares

I'm struggling something immensely to make sense of the following: https://meiji163.github.io/post/sum-of-squares/#sums-of-two-squares Factoring an integer in Gaussian integers is closely related to ...
• 1,992
1 vote
90 views

### The chunking aspect of repunit prime factors [closed]

While others have already mentioned the divisibility of decimal repunits, $$m := \frac{{10}^n - 1}{9}.$$ ...
1 vote
91 views

### Will there be infinity prime numbers of the sort $a^2 -2$ (where $a$ is odd)?

Will there be infinity prime numbers of the sort $a^2 -2$ (where $a$ is odd)? To begin with, every odd composite number can be written as $a^2$ or as $a_{x}^2 -a_{y}^2$ as long as either $x$ or $y$ ...
• 1,415
91 views

### Problem in understanding the unique factorization theorem for Euclidean Rings.

Unique Factorisation Theorem: Let $R$ be a Euclidean ring and $a\neq 0$ non-unit in $R.$ Suppose that $a =\pi_1\pi_2\cdots\pi_n=\pi_1'\pi_2'\cdots\pi_m'.$ where the $\pi_i$ and $\pi_j'$ are prime ...
• 2,788
1 vote
46 views

### Unique unramified ideal implies that the ramification index is equal to the degree of field extension in a galois extension

Given a Galois extension $K \supseteq \mathbb{Q}$, prove that if there is only one unramified prime number $p$ over $K$ then there is only one prime ideal $\mathfrak{p} \subseteq O_K$ containing $p$ ...
• 362
57 views

### Can you prove that 2^n-1 will be divisible by 3 if n is even. [duplicate]

Can you prove that 2^n-1 will be divisible by 3 if n is even. I have generated this: ...
59 views

• 621
142 views

### What are the next primes/semiprimes of the form $\frac{(n-1)^n+1}{n^2}$?

This question is inspired by this question For an odd positive integer $n$ , define $$f(n):=\frac{(n-1)^n+1}{n^2}$$ as in the linkes question. For which $n$ is this expression prime , for which $n$ ...
• 84.7k
1 vote
42 views

### Factorization of Proth numbers with $k=1$

This is more of a practical question, for anyone out there who might know where to start. I'm looking for a complete factorization of numbers of the form $2^n+1$ for positive integers $n$. Essentially ...
93 views

### Splits completely of a prime ideal

Suppose that $K$ is a number field and $\mathfrak p$ is a prime ideal non-zero. In general always exists a finite extension of $L$ of $K$ such that $\mathfrak p$ is ramified, for example $L=K(\sqrt f)$...
223 views

• 23.6k
80 views

### If $x^2\equiv y^2\mod n$, does $\gcd(x-y,n)$ divide $n$? [duplicate]

If $x^2\equiv y^2\mod n$, does $\gcd(x-y,n)$ divide $n$? EDIT: I should really be asking if $\gcd(x-y,n)$ is neither $n$ nor $1$, since it will always divide $n$. I know $n$ must divide $x^2-y^2$, ...
96 views

62 views

### What percentage of numbers can be written as $n=p*m$ with p prime and $p>m$

What is the chance* that a random positive integer $n$ is the product of a prime $p$ and an integer $m>0$, with $p>m$ Or in other words: when $n$ has a prime factor greater than it's square root ...
284 views

### Can factoring $90$ help factor $91$?

There are few posts asking if factoring $N-1$ can help factor $N$. In those posts the focus was on the factors of $N-1$ and $N$ which can never be the same. The conclusion therefore was that ...
• 1,048
204 views

### A question about prime factorization of composite Mersenne numbers and $(2^p-2)/(2 \cdot p)$

Mersenne numbers are numbers of the form $2^p-1$ where $p$ is a prime number. Some of them are prime for exemple $2^5-1$ or $2^7-1$ and some of them are composite like $2^{11}-1$ or $2^{23}-1$. I'm ...
• 131
254 views

### Prime factors of $5^n+6^n+7^n+8^n+9^n+10^n$

I currently run an integer factoring project of the numbers of the form $$5^n+6^n+7^n+8^n+9^n+10^n$$ where $n$ is a non-negative integer. Do the prime factors have a particular form as it is the case ...
• 84.7k
### Is $\omega(n)=16$ the maximum?
What is the largest possible value of $\omega(n)$ (the number of distinct prime factors of $n$) , if $n$ is a $30$-digit number containing only zeros and ones in the decimal expansion. I checked ...