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
2
votes
1answer
21 views

Examples of quadratic extensions K, L of $\mathbb{Q}$ such that KL has some properties.

Let $p$ be a prime integer, I want to find $p$ and K, L extensions of $\mathbb{Q}$ such that K, L contain each a unique prime lying over $p$ but KL does not The residue field extension of $\mathbb{...
0
votes
1answer
31 views

For any positive integer n, let d(n) denote the number of positive divisors of n; and let φ(n) denote the

For any positive integer n, let d(n) denote the number of positive divisors of n; and let φ(n) denote the number of elements from the set {1, 2, · · · , n} that are coprime to n. (For example, d(12) = ...
2
votes
2answers
70 views

Equations involving particular values of the Dedekind psi function and powers of the kernel function

In this post we denote the Dedekind psi function as $\psi(m)$ for integers $m\geq 1$. As reference I add the Wikipedia Dedekind psi function, and [1]. One has the definition $\psi(1)=1$, and that the ...
-1
votes
0answers
56 views

How to find the numbers of factor $2s$ in $2048!$

As stated in the title. I tried the prime factorisation of $2048\times 2047\times 2046 \times \cdots$, but observed no strict patterns in the $2^{(n)}$ (e.g. $2048=2^{11}$,$2047$ is not factorsible ...
0
votes
1answer
28 views

If $a+bc$ and $c$ have irreducible factors in common, then $a$ and $c$ have the same irreducible factors in common.

Let $a,b,c \in K[t]$ where $K$ is field with characteristic not $2$ or $3$ and see title for the question. This is a problem I encountered in showing the image of some map is finite, which I need in ...
1
vote
0answers
58 views

Prove or disprove that $\frac{(x+n)!}{x!}$ is not divisible by $n$ distinct primes where each prime is greater than $\frac{(x+n)e}{n}$

Is it true that for integers $n > e, x \ge n$, it is impossible for $\dfrac{(x+n)!}{x!}$ to be divisible by $n$ distinct primes where each prime is greater than $\dfrac{(x+n)e}{n}$? Example: $x=n=...
0
votes
1answer
43 views

If $m > n$ are coprime, then there (often) exists $p$, $q$ where $mq+1=n^p$. why?

One of the key reductions in Shor's algorithm in quantum computing for finding prime factors of $m$ is that if $n < m$ is coprime with $m$, then there likely exists integers $p$ and $q$ where $mq+...
3
votes
2answers
60 views

Finding prime factors of $2^{300} - 1$

My initial approach to this problem was to use Fermat's Little Theorem: We seek primes $p$ such that $2^{300} \equiv 1 \pmod{p}$. By Fermat's Little Theorem, if $a^{p-1} = 2^{300}$ for some prime ...
0
votes
3answers
84 views

Euler's product formula in number theory

Is there intuitive proof of Euler's product formula in number theory (not searching for probabilistic proof) which is used to compute Euler's totient function?
3
votes
0answers
55 views
+50

Prime decomposition of pR in $\mathbb{A}\cap \mathbb{Q}[\alpha]$ for $\alpha={^3\sqrt{hk^2}}$ if p is a prime such that $p^2|m$

I'm going through Marcus number Field chapter 3 an I'm finding very hard to understand the part about the decomposition of pR (theorem 27) that tells us that if $p\not||R/Z[\alpha ]|$ then we can ...
0
votes
1answer
27 views

Prime decomposition of pR where R=$\mathbb{A}\cap \mathbb{Q}[\alpha]$ with $\alpha^5=5(\alpha+1)$, exercise 27 chapter 3 of Marcus

I'm trying to do exercise 27 in chapter of Marcus but it seems to me there is a typo or maybe it's me not understanding. The exercise is the following Let $\alpha^5=5(\alpha+1)$ R=$\mathbb{A}\cap \...
1
vote
2answers
76 views

Probability a natural number of the form $m^2 - n^2$ can be exactly factored as the product of $2$ primes?

Question Let $P$ be the probability that two integers where $m>1$is a fixed positive integer and $n$ is a randomly chosen such than $ m> n \geq 0 $? What is the probability $m^2 -n^2$ is ...
1
vote
2answers
31 views

Finding all no-congruent primitive roots $\pmod{29}$

Finding all no-congruent primitive roots $\pmod{29}$. I have found that $2$ is a primitve root $\pmod{29}$ Then I found that is it 12 no-congruent roots, since $\varphi(\varphi(29)) = 12$ Then I ...
1
vote
1answer
34 views

Prove that, for every natural number, their factorization as primes is unique

I need some feedback on this proof I wrote that: $$\forall n\in\mathbb{N} \text{ assumed the existence of a factorization of } n \text{ as } n = p_1p_2\cdots p_k, \text{ where } p_i, (1 \leq i \leq k)...
-1
votes
0answers
24 views

problem solving- prime decomposition [closed]

The proper factors of a number n are the factors which are less than n. A number n is deficient if the sum of its proper factors is less than n. For example, 22 is deficient since 1 + 2 + 11 = 14 < ...
0
votes
1answer
30 views

Primes which can be Norms vs Primes which Split Completely in Galois Extensions

Let $K/ \mathbb Q$ be a Galois extension. I read somewhere that the integer primes $p$ which can be norms of some integral ideal $\mathfrak a$ of $k$ are exactly the ones which split completely in $K$,...
-1
votes
0answers
9 views

Give a prime factorisation of $10 ∈ Z[i]$ justifying why each factor is prime.

Assuming that $Z[i]$ is a Euclidean domain, and that the Euclidean function $ν(a + ib) = a^2 + b^2$ is multiplicative, how would you be able to give a prime factorization of $10 ∈ Z[i]$ ?
4
votes
2answers
84 views

Application of the decomposition of prime ideals as $Q_q^{e_1}Q_2^{e_2}\dots Q_R^{e_r}$

I'm reading Marcus number field book and at page 57 he asks the following We give some applications of Theorem 27. Taking $\alpha=\sqrt{m}$, we can re-obtain the results of Theorem 25 except when ...
3
votes
1answer
67 views

Principal generators of prime ideals is $\mathbb{Q}[\sqrt{m}]$ for m=-1, -2, -3

I'm reading Marcus "Number fields" book and at a certain point (page 52) in the chapter about prime decomposition he writes We now consider in detail the way in which primes p $\in \mathbb{Z}$ ...
0
votes
1answer
26 views

Does any number, p, have a number of prime factors greater than ln(p)?

I've wrote a very silly algorithm for prime decomposition, but I can't be certain that it works unless I can find a bound $K(p)$ such that for any number, $p$, the number of prime factors of $p$ is ...
1
vote
1answer
57 views

Marcus,problem 12, chapter 3

I'm trying to solve this exercise from Marcus' book "Number fields". Following Marcus notation, let me call $S=\mathbb{Z}[\alpha]$, where $\alpha=\sqrt[3]{2}$, and $R=\mathbb{Z}$. Firstly I proved ...
0
votes
0answers
44 views

What do Mersenne Primes have to do with record sum of factors?

The Set Up: I was studying this sequence which can be described as follows. Call the linked sequence $a(n)$. We define $b(n)$ a related sequence first linked here: $$ b(n) = \text{largest k} | \...
1
vote
1answer
25 views

Fermat factorization and primality proving

In Fermat factorization you can factor an integer $n$ if you find a nontrivial pair $(x,y)$ such that $x^2\equiv y^2 \mod n$. At the end of the description in https://mathworld.wolfram.com/...
0
votes
1answer
29 views

Does there always exist a prime $q\equiv3\mod 4$ that divides $p+a^2$ with $p\equiv1$ mod 4

Let $p$ be a prime such that $p\equiv1\mod4$. Is it true that there will always exist a prime $q$ that satisfies $q\vert(p+a^2)$ and $q\equiv3\mod4$, for some integer $a$? I have tried proceeding by ...
1
vote
0answers
38 views

RSA Number Factorization - question regarding polynomial validity

I am interested in factorizing RSA numbers as a coding challange. I understand the basic principle that $2$ large primes are multiplied together to generate the specific RSA number, however I also see ...
0
votes
1answer
44 views

Is this a novel factorization theorem? Solving $\sin^2(\pi x)+\sin^2\left(\frac{\pi p}{x}\right)=0$ for $x$ gives the integer factors of $p$.

I have found that $$ \sin^2(\pi x) + \sin^2\left(\frac{\pi p}{x}\right)=0 $$ solved for $x$ defines the integer factors of $p$. Iteratively applied it also defines the prime numbers smaller than $n$ ...
0
votes
0answers
26 views

Does it follow that there are at most $n+\pi(n-1)$ distinct primes that divide $\dfrac{(x+n)!}{x!}$

I've been thinking about the total number of distinct primes and it occurred to me that for any integers $x > 0, n > 0$, there are at most $n+\pi(n-1)$ distinct primes that divide $\dfrac{(x+n)!}...
0
votes
2answers
59 views

Why is $x^{\frac{n-1}{2}}\not \equiv 1 \mod n$

If $n=p_1p_2\cdots p_r$ and $g_1$ is the generator of $U(Z_{p_1})$. Then let $x$ be an integer such that $x\equiv 1 \mod p_2p_3\cdots p_r$ and $x\equiv g_1\mod p_1$ I would like to prove that $x^{\...
0
votes
1answer
55 views

An Olympiad math problem about prime numbers [duplicate]

Let $x,n ∈ \mathbb{N}$ such that : $1+x^1+x^2+x^3+\dots +x^{n-1}$ is prime . Proof that $n$ is prime . I actually suppose that $n$ isn't prime absurdly so $n=p×k$ such as $p$ is prime, I also use ...
0
votes
0answers
30 views

How can i show that the sum $\sum^{p-1}_{i=0}(-2)^{iq}$ is not a prime number?

I need to show that $\sum^{p-1}_{i=0}(-2)^{iq}$ is not a prime number, where p is a prime number greater than $5$ and $q$ a number such as $p \nmid q$. As a try, i thought that this stands for every $...
0
votes
0answers
39 views

Expected number of prime factors of a number

Given the formula for the expected amount of numbers $k$ less than $x$ such that $k$ has exactly $n$ prime factors, can we use the formula of the expected value to give an equation that gives the ...
0
votes
1answer
40 views

How I can prove that $p$ is always a factor of factorization of this number $N=pp\cdots$? [closed]

Assume we have a prime number $p=37$ , I want a such proof in number theory such that $p$ must be a prime factor of this number $N=pp\cdots$, I have used proof Euclid which it showed infinity many ...
0
votes
0answers
25 views

Existence of Prime Factor with Ramification Index 1

I have been studying some basic ramification theory, and, given the standard "$AKLB$ configuration", - where $A$ is a Dedekind Domain with field of fractions $K$, $L$ a finite separable extension of $...
1
vote
1answer
38 views

Is the following an existing conjecture or a conjecture at all?

the following floated to my mind today, can you verify if it stands to be true, or is a pre-existing conjecture. If not, can you correct me? And if it is one, can you prove it? Prime factorisation of ...
2
votes
0answers
46 views

How to find polynomial $f\in \mathbb{Z}[x]$ with small coefficients, such that $f(m) = 0 \pmod{n})$?

Let $n$ be an integer number, such that $n= p_1 p_2 p_3 \cdots p_k$, where $p_1, p_2, \ldots, p_k$ are not necessarily distinct prime numbers and $k>2$. Also, let $m$ be a given natural number. ...
0
votes
0answers
29 views

Distribution of composite numbers with $n$ prime factors

Similar to how the Prime Number Theorem approximates the number of primes less than some value $x$, is there a theorem/function that approximates the number of composite numbers with exactly $n$ prime ...
0
votes
0answers
12 views

Hard problems that do not require predefined parameters

(A) Is the following problem hard (i.e. no known solution in polynomial time)? For large values of $N$ and $M$ (e.g. $N \ge 4096$, $M \ge 130$), find values for $g,x,c,p$ and $q$ such that: $ g^x \...
0
votes
0answers
13 views

Factoring an ideal in a quotient polynomial ring

I have been asked to show a number of facts about the quotient ring $\mathbb{F}_5[X,Y]/(Y^2-X^3+1).$ One of the first things I'm asked to do is find the factorization of the ideal $(X-1)$ in this ...
2
votes
3answers
103 views

Basic number theory

I am doing my thesis on elliptic curves right now and in the meantime this lemma showed up: Suppose $a$ and $b$ are integers such that $ab = m^3$ for some integer $m$. Let $d = \operatorname{gcd}(a,...
0
votes
0answers
20 views

Numbers that equal the sum of prime factors of their digit reversal

Let $\text{reverse}_{10}(n)$ be the digit reversal (in base 10) of $n$, and let $\text{sopfr}(n)$ be the sum of $n$'s prime factors, with repetition. What numbers $x$ exist such that $x = \text{sopfr}(...
6
votes
2answers
78 views

Why do all primes in Fibonacci numbers repeat so regularly

I watched this YouTube video that is mainly about primes as factors of the Fibonacci numbers. It notes that every Fibonacci number after F(12) has a new prime factor not previously seen, and this new ...
0
votes
2answers
22 views

Formula for the sum of distinct prime factors of $n$

This seems like a simple question, but I have been searching the internet forever to find an answer. Is there a formula for the sum of the distinct prime factors of a given positive integer $n$?
0
votes
0answers
27 views

Is there a simple formula for the sum of divisors? [duplicate]

Say I’m given the prime factorization of a number N is there a formula that allows me to calculate the sum of the number divisors?
2
votes
1answer
121 views

Does a graded poset on $\mathbb{N}_{>0}$ generated from subtracting factors define a lattice?

Consider the partial ordering of positive integers with covering relations $n - \frac np \lessdot n$ for all prime divisors $p \mid n$. This defines a graded poset with $A064097$$(n)+ 1$ rank levels ...
2
votes
2answers
65 views

Find all prime numbers that divide 2 polynomials

I am trying to pass some time during the COVID-19 era. I was going through my mails and found a problem. A friend of mine said her daughter had this problem in some math contest about 2-3 years ago ...
2
votes
1answer
36 views

Determining the parity (even or odd) of pi notation

I am trying to disprove a conjecture, and I have gotten it such that the conjecture is only true if $$\prod_{i=1}^{g}{(\frac{j_i^{L_i+1}-1}{j_i-1})}$$ is singly even (of form $2m$ where $m$ is odd). ...
3
votes
0answers
27 views

What is the smallest rectangle that could fit all the mentioned rectangles without overlapping?

If there are n rectangles, each with the size 1×2, 2×3, 3×4, 4×5 ... n(n+1), what would be the smallest rectangle in which we could fit all n of these rectangles without any of them being overlapped? ...
1
vote
0answers
35 views

Computing the prime factorization of a sum of two integers when their individual prime factorizations are known

If the prime factorization of two numbers is known, does a method exist to find the prime factorization of their sum with an asymptotic complexity better than the general prime factorization problem? ...
0
votes
1answer
27 views

Proof for formula for number of divisors

For any natural number $n>1$, with factorization $$ n = q_1^{\alpha_1}q_2^{\alpha_2}q_3^{\alpha_3}....q_m^{\alpha_m} $$ we can find the number of divisors by using the formula, $$ (\alpha_1+1)(\...
0
votes
1answer
17 views

Is this finite field arithmetic?

I just found out about finite fields because of AES but I think it's may have illuminated something about the Pollard Rho Brent prime decomposition algorithm for me: ...

1
2 3 4 5
32