# Questions tagged [prime-factorization]

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

1,326 questions
23 views

### Is it possible to find a multiple knowing only: the count of its divisors, the upper limit and some of its divisors (more details)?

In other words, say I am looking for multiple X let: X < 1000005 let the fist 18 divisors of X be: 1 | 2 | 4 | 5 | 8 | 10 | 16 | 20 | 25 | 32 | 40 | 50 | 64 | 80 | 100 | 125 | 160 | 200 ...
27 views

### Prove if $n\geq 9$ than $P_n> 2n+3$, p is a prime [duplicate]

Using mathematical induction if n=9 then: $p_9 >18+3$ i.e 23>21 (true) let it is true for m $p_m>2m+3$ but for m+1, how do you prove it? I am not getting m+1 th term. Or, if there is ...
25 views

### For $a, b$ coprime, if $p \geq 5$ is a prime which divides $a^2 - ab + b^2$, then $p \equiv 1 \pmod{6}$ [duplicate]

Equivalently, prove that -3 is a quadratic residue for any prime divisor $p$ of $a^2 - ab + b^2$, assuming $(a,b)=1$. I read the answers to questions like this one, which cover the case $b = \pm 1$, ...
20 views

### In the rational Sieve method why does n = gcd(a-b,n)×gcd(a+b,n) exactly?

As a quick notation explanation of the basic rational sieve method, a set of primes $P$ that are coprime to a number $n$ tested for primality are chosen randomly as follows(from wikipedia): Suppose ...
42 views

### Proof of failure of unique factorization of 4K+1

For the prime number in 4K+1, number 9, 21, and 49 are in the set of prime number. But it’s uniqueness of factorization fail because 9*49=21*21. What is the mathematic reason prove that 4K+1 fail the ...
57 views

49 views

### How can I solve this proof? (Prime factorization)

Let $p_1, p_2, ... , p_n$ be $n$ distinct primes. Prove that for all $x ∈ \Bbb{Z}$ we have $p_i | x$ for all $i ∈ \{1,2, ... , n\}$ if and only if $(p_1*p_2* ...*p_n)|x$. Hello. I'm very lost in ...
42 views

### Finding general formula and prime factorisation

Let A denote the set of all positive even integers. We call a number a in A “magic" if a cannot be expressed as a product of two other members of A. I have found a general form for this series a=4x-y,...
61 views

### Efficiently (by hand) determining principal prime ideals lying over a given prime in $\Bbb Z$. $\Bbb{Q}(\sqrt{5})$.

Let $K=\Bbb{Q}(\sqrt{5})$ and consider the ring of integers $\Bbb{Z}\left[\frac{1+\sqrt{5}}{2}\right] = \mathcal{O}_K\subset K$. I want to explicitly determine the prime ideals of $\mathcal{O}_K$ ...
20 views

91 views

48 views

### Arbitrarily large sequence of numbers with a property

We say that a positive integer is good if it has an even number of prime factors. Does there exist an arbitrarily large sequence of consecutive good numbers? In fact, this problem came from another ...
34 views

### Is it possible to convert factorization problem into discrete logarithm problem and vice versa?

You can see at this link wiki: Discrete_logarithm#Algorithms that some algorithms for factorization of numbers can be used to solve discrete logarithm problem. Can you give me an explicit example how ...
27 views

### Factorization and the difference of two squares

While contemplating on the mathematics behind RSA cryptography, I tried to play around how to possibly find the factors $p,q$ in a rather more algebraic and elementary way. What I initially found out ...
81 views

103 views

### Every natural number $n$ can be written as $n=s-t$ with $\omega(s)=\omega(t)$ [on hold]

Can we prove the following statement ? Every natural number $n$ can be written as $n=s-t$ ($s,t$ positive integers) with $\omega(s)=\omega(t)$ , in other words , the difference of two ...
114 views

### Odd numbers with $\varphi(n)/n < 1/2$

The topic was also discussed in this MathOverflow question. From $\varphi(n)/n = \prod_{p|n}(1-1/p)$ (Euler's product formula) one concludes that even numbers $n$ must have $\varphi(n)/n \leq 1/2$ ...
179 views

### Can the sum of two squares be used to determine if a number is square free?

Mathword (http://mathworld.wolfram.com/Squarefree.html) stated that "There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer."...
59 views

### Relation between The Euler Totient, the counting prime formula and the prime generating Functions [closed]

](https://i.stack.imgur.com/lKFS0.png) Relation between The Euler Totient, the counting prime formula and the prime generating Functions There is a formula for the ivisor sum hiih is one of the ...
100 views

### If a prime $p$ divides $n^2$ then it also divides $n$ - Is this proof correct?

I'm learning Real Analysis by myself and I wanted to prove that if a prime $p$ divides $n^2$ where $n$ is an integer, then $p$ divides $n$ itself. I saw that proving this is the same as saying that ...
64 views

### How to express 80^2/3 as a product of powers of prime numbers

So the given was: $(80)^\frac23(25)^\frac32$ and I was told to simplify and express as a product of powers of prime numbers. Now I'm not very familiar with this product of powers of prime numbers so ...
35 views

### Assuming X = A + B * C, where A & B are integers, C is irrational; Find A & B given X & C

I'm looking for an efficient algorithm which can solve this problem. Can I do better than with the following brute force algoritm in C++? ...
### Conditions for solutions to $p^a = q^b$
When (for what conditions on $p,q$) can we solve this equation for integers. I know that $p = q^b$ can only be solved when $p$ is an integer to the power of $b$. By analysing the prime factorisation ...
### Probability for composite $n$ to have prime factor $\geq \sqrt n$
Let $\operatorname{GPF}(n)$ denote the largest prime factor of $n\in\mathbb N_{>1}$. My computer tests for intervalls $[m,n]$, where $n<10,000,000$, suggests that the probability \$\operatorname{...