Skip to main content

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
-1 votes
0 answers
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$ ...
user1308446's user avatar
1 vote
1 answer
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 ...
Eric's user avatar
  • 145
0 votes
0 answers
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 ...
Penguino's user avatar
  • 1,189
1 vote
1 answer
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 ...
Alex Tbk's user avatar
  • 121
2 votes
2 answers
91 views

How to describe integers with the same prime factors?

Is there a term for the relationship between two integers that have the same prime factors? For example, $6=(2)(3)$ and $12=(2)(2)(3)$. Can one describe this with something along the lines of "$...
mathbeing's user avatar
3 votes
2 answers
209 views

Two questions around some new card game based on prime factorization.

I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...
mathoverflowUser's user avatar
6 votes
0 answers
96 views

Factorizations not sharing digits with original number

The sequence A371862 is "Positive integers that can be written as the product of two or more other integers, none of which uses any of the digits in the number itself." In the extended ...
Ed Pegg's user avatar
  • 21.2k
0 votes
2 answers
65 views

prime factorization in $\mathbb{Z}[i]$ [duplicate]

We were asked to show where the following reasoning goes wrong. Since $1+i$ and $1-i$ are prime elements in $\mathbb{Z}[i]$, the equation $$(-i)(1+i)^2=(1+i)(1-i)=2$$ show that unique prime ...
riescharlison's user avatar
4 votes
0 answers
99 views

Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$

As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
Juan Moreno's user avatar
  • 1,110
26 votes
1 answer
522 views

Prime factor wanted of the huge number $\sum_{j=1}^{10} j!^{j!}$

What is the smallest prime factor of $$\sum_{j=1}^{10} j!^{j!}$$ ? Trial : This number has $23\ 804\ 069$ digits , so if it were prime it would be a record prime. I do not think however that this ...
Peter's user avatar
  • 84.7k
0 votes
0 answers
35 views

Approximating a rational number in a subset of Q defined by limited prime factors

I'm wondering if there is an efficient (or good enough for small numbers) algorithm for the following problem: Suppose I have a rational number in the form of its prime factorization: $k = p_0^{x_0}...
retooth's user avatar
3 votes
1 answer
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 ...
Juan Moreno's user avatar
  • 1,110
0 votes
0 answers
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 ...
Adam Rubinson's user avatar
2 votes
1 answer
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 ...
MathArt's user avatar
  • 175
1 vote
1 answer
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 ...
Larry Freeman's user avatar
0 votes
1 answer
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)$ ...
Larry Freeman's user avatar
1 vote
1 answer
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$ ...
Juan Moreno's user avatar
  • 1,110
0 votes
0 answers
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 ...
852619's user avatar
  • 43
0 votes
0 answers
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? ...
NCY's user avatar
  • 37
1 vote
0 answers
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 ...
StormyTeacup's user avatar
  • 1,992
1 vote
0 answers
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}.$$ ...
RARE Kpop Manifesto's user avatar
1 vote
1 answer
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$ ...
Isaac Brenig's user avatar
  • 1,415
3 votes
1 answer
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 ...
Thomas Finley's user avatar
1 vote
1 answer
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$ ...
RHspqr's user avatar
  • 362
-1 votes
1 answer
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: ...
Gal Lahat's user avatar
0 votes
0 answers
59 views

Prime number $p$ such that $p+1$ has all given prime numbers as prime factor.

For given finite prime numbers set $P$, does there exist some prime number $p$ such that for any $\ell\in P$, $\ell\mid (p+1)$? For example, if $P=\{2,3,7\}$, then we can take $p=41$. In this case, $(\...
Yos's user avatar
  • 1,924
3 votes
3 answers
220 views

For what integers $n$ does $\varphi(n)=n-5$?

What I have tried so far: $n$ certainly can't be prime. It also can't be a power of prime as $\varphi(p^k)=p^k-p^{k-1})$ unless it is $25=5^2$. From here on, I am pretty stuck. I tried considering the ...
Jason Xu's user avatar
  • 621
2 votes
0 answers
55 views

What did I get wrong in this Mobius function question? [closed]

$f(n):=\sum\limits_{d\mid n}\mu(d)\cdot d^2,$ where $\mu(n)$ is the Möbius function. Compute $f(192).$ First, I found all of the divisors of 192 by trial division by primes in ascending order: $D=\{...
Jason Xu's user avatar
  • 621
4 votes
0 answers
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$ ...
Peter's user avatar
  • 84.7k
1 vote
1 answer
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 ...
Dachs Luchsinger's user avatar
0 votes
1 answer
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)$...
Luis Antonio Sanchez's user avatar
2 votes
2 answers
223 views

Minimising $x+y$ in $x^y=a$

Regarding this recent question, the question asks for minimizing $x+y$, given $x^y=a$, (for a constant real positive $a$) for real and positive values of $x$ and $y$. Now $(x,y)=\left(\exp\left({2W\...
Soham Saha's user avatar
  • 1,290
1 vote
0 answers
111 views

Plot of the ratios of Goldbach pairs

Preface I was playing around with matplotlib to generate some number sequences. I wound up looking at Goldbach pairs and manipulating them in different ways. End result was the following plots. I can'...
Mudsy's user avatar
  • 11
2 votes
2 answers
141 views

Finding positive integer $n>10$ that maximizes $\frac{\sigma_0(n)}{2^{\log n}}$

Among all the positive integer, which one integer, $n$, can make the number below the largest? $$f(n)=\frac{\sigma_0(n)}{2^t}$$where $t=\log_{10}n$ and $\sigma_0$ is the divisor function. For example,...
A Math guy's user avatar
2 votes
1 answer
61 views

Asymptotic Approximation towards Sum of the Composite Number's Smallest Prime Factor

I wonder if there is any asymptotic approximation towards the sum of the smallest prime factor of the composite numbers which are less than $n$. This is also the sum of terms whose index is not prime ...
nik_nul's user avatar
  • 21
2 votes
1 answer
73 views

What are the other factors of x if we know 2, 4, and 9 are factors. [closed]

The factors of x include 2, 4, 9. Which of the following are also factors of x? {1, 3, 5, 6, 8, 10, 12, 18, 24, 36} Apparently the correct answer is {1, 3, 6, 12, 18, and 36} but I have trouble seeing ...
Ian Salinas's user avatar
1 vote
1 answer
80 views

How many different squares are there which are the product of six different integers from 1 to 10 inclusive?

How many different squares are there which are the product of six different integers from 1 to 10 inclusive? A similar problem, asking how many different squares are there which are the product of six ...
eee's user avatar
  • 45
6 votes
4 answers
1k views

Fundamental Theorem of Arithmetic - Is my proof right?

My goal was to prove the Fundamental Theorem of Arithmetic without using Euclid's Lemma. There are some proofs online but I haven't found one that uses this idea, so I want to make sure it's right. ...
adam7's user avatar
  • 61
6 votes
1 answer
132 views

Conjecture: $\prod\limits_{k=0}^{n}\binom{2n}{k}$ is divisible by $\prod\limits_{k=0}^n\binom{2k}{k}$ only if $n=1,2,5$.

The diagram shows Pascal's triangle down to row $10$. I noticed that the product of the blue numbers is divisible by the product of the orange numbers. That is (including the bottom centre number $...
Dan's user avatar
  • 23.6k
0 votes
1 answer
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$, ...
Cotton Headed Ninnymuggins's user avatar
2 votes
1 answer
96 views

Show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs

I am trying to show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs. I'm pretty sure this is true but I don't see how to prove it. There is no obvious way to use induction. Here is an example: $...
Clyde Kertzer's user avatar
2 votes
1 answer
146 views

Factoring 319375146 without a calculator

The goal is to factor $N = 319375146$ without a calculator, using only pencil and paper in under 30 minutes. The exact question is "What is the 4 digit prime factor of 319375146?" This comes ...
Display name's user avatar
  • 5,202
2 votes
0 answers
59 views

Is my proof of the divergence of prime reciprocals valid

I tried to prove the divergence of the prime reciprocals as a challenge and I think I came up with quite an intuitive argument using Borell Cantelli, but maybe not rigorous. For two primes $p_n>...
AndroidBeginner's user avatar
2 votes
0 answers
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 ...
AndroidBeginner's user avatar
2 votes
0 answers
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 ...
user25406's user avatar
  • 1,048
3 votes
1 answer
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 ...
Aurel-BG's user avatar
  • 131
2 votes
2 answers
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 ...
Peter's user avatar
  • 84.7k
0 votes
0 answers
51 views

Found a relation regarding the primes, is this interesting?

Define $S_{odd}$ as all $n\in N $ where $n$ is the product of an odd number of distinct primes. Define $S_{even}$ similarly. Thus: $$S_{odd} = \{2,3,5,...,30,42,....\}$$ $$S_{even} = \{6,10,14, ....,...
AndroidBeginner's user avatar
-1 votes
1 answer
82 views

Dottie number and prime factorization

It's related to Dottie number and prime factorization . Let : $D=\operatorname{Dottie-number}\simeq 0.7390851332$ Now define $n\geq 3$ an integer: $$\lfloor\left(D\right)^{-2n}\rfloor=P$$ Then it ...
Miss and Mister cassoulet char's user avatar
2 votes
1 answer
94 views

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 ...
Peter's user avatar
  • 84.7k

1
2 3 4 5
42