Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [prime-factorization]

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

0
votes
2answers
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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$, ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
5
votes
3answers
57 views

Proof for bijection of a function between positive integers and nonprime positive integers.

Exercise 4.39 on Concrete Mathematics mentioned a function $S(m)$: Let $S(m)$ be the smallest positive integer $n$ for which there exists an increasing sequence of integers $$ m = a_1 < a_2 &...
2
votes
2answers
33 views

Adding a number to one of prime factors to produce greatest value

I recently found an interesting question that I had hard time figuring out. The question states as follows: If 20 were to be added to one of the five prime factors (103)(113)(131)(109)(139) then ...
4
votes
1answer
79 views

Prime factorization of

For a positive integer $k$, let $S_k$ be the set of numbers $n > 1$ that are expressible as $n = kx + 1$ for some positive integer $x$. The set $S_k $ is closed under multiplication. That is: If $...
1
vote
1answer
31 views

What can be said about the prime decomposition of the Bezout coefficients $\beta(a,b)$?

Let $a, b$ be coprime rational integers. Then by Bezout's lemma we can find $(s,t) := \beta(a,b) \in \mathbb{Z}^2$ such that $a*s + b*t = 1$. My question concerns the prime factorization of the ...
2
votes
1answer
45 views

Factorization of large (60-digit) number

For my cryptography course, in context of RSA encryption, I was given a number $$N=189620700613125325959116839007395234454467716598457179234021$$ To calculate a private exponent in the encryption ...
36
votes
1answer
2k views

Is there any other number that has similar properties as $21$?

It's my observation. Let $$n=p_1×p_2×p_3×\dots×p_r$$ where $p_i$ are prime factors and $f$ and $g$ are the functions $$f(n)=1+2+\dots+n$$ And $$g(n)=p_1+p_2+\dots+p_r$$ If we put $n=21$ then $$g(f(21)...
1
vote
2answers
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 ...
1
vote
1answer
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,...
5
votes
1answer
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$ ...
1
vote
0answers
20 views

Calculating $\sum_{1 \leq j \leq i, \gcd(i, j) > 1} \gcd(i, j)$ for some i

As title, is there a way to simplify the sum $\sum_{1 \leq j \leq i, \gcd(i, j) > 1} \gcd(i, j)$ for some given $i$? I have tried to write $i$ into its prime factorisation $\prod_{i=1}^{k}{p_i}^{...
1
vote
2answers
43 views

Proving the divisibility of $4[(n-1)!+1]+n$ by $n(n+2)$ in the condition of $n,n+2 \in P$ where $P$ is the set of prime numbers [duplicate]

Let $n$ and ($n+2$) be two prime numbers. If any real value of $n$ satisfies that condition, then prove that $$\frac{4{[(n-1)!+1]}+n}{n(n+2)} = k$$ where $k$ is a positive integer. SOURCE: BANGLADESH ...
1
vote
1answer
35 views

Numbers with exactly 1 square (prime) factor

I have recently learned that numbers with no square (prime, assumed in the following) factor are called square-free numbers. I have read that it would asymptotically grows towards $$\#\{SquareFree\} ...
4
votes
3answers
132 views

Numerical example for $\gcd(a,b)=\prod p_i^{\min(a_i,b_i)}$

I'm actually having trouble understanding the above corollary. Can anyone please provide a numerical example of that corollary? Thank You So Very Much in advance. Corollary If $a=\prod p_i^{a_i}$ ...
1
vote
1answer
44 views

How exactly does finding a square root of $1$ modulo $N$ enable us to factor $N$?

The Wikipedia article on Shor's algorithm says: The aim of the algorithm is to find a square root $b$ that is different from $1$ and $-1$; such a $b$ will lead to the factorization of $N$, as in ...
6
votes
1answer
134 views

Density of integers $n$ with all prime factors of order $O(\log n)$?

For a rational integer $n \in \mathbb{Z}_{+}$, let $\mathfrak{p}(n)$ denote the set of (distinct) prime factors of $n$. Then for a positive constant $c$, let $$f(x) = \vert\{n\in\mathbb{Z}_{+}:\ n\...
2
votes
0answers
47 views

Why are polynomials of even powers better for Pollard's rho?

Taking all $C(900,2)$ combinations of the first 900 prime numbers, I defined $N = pq$, where $p$ and $q$ are a combination of primes. Then I factored $N$ using Pollard's Rho, counting how many ...
2
votes
1answer
47 views

Factoring a large semi-prime number.

Say I want to factor $N=12193263122374638001$ into prime factors. Surely this can easily be done with a computer and the answer would be $N=123456789\cdot9876543211.$ But If I want to do this by hand,...
0
votes
0answers
43 views

Factorising numbers (~200 digits) methods.

are there any mathematical methods used to factorize huge integers(around 200 digits)? I'm doing that in Python, by the way. Also, if I ever get around a proper algorithm to do it, how much time ...
4
votes
1answer
62 views

How to prove that there are infinitely many primes of form $6n+1$? [duplicate]

We know that all primes greater than $3$ are of form $6n+1$ or $6n-1,$ but how do I prove that there are infinitely many of the form $6n+1$? Please prove it without Dirichlet's theorem. Note: This ...
1
vote
2answers
94 views

Factor $x^8-x$ in $\Bbb Z[x]$ and in $\Bbb Z_2[x]$

Factor $x^8-x$ in $\Bbb Z[x]$ and in $\Bbb Z_2[x]$ Here what I get is $x^8-x=x(x^7-1)=x(x-1)(1+x+x^2+\cdots+x^6)$ now what next? Help in both the cases in $\Bbb Z[x]$ and in $\Bbb Z_2[x]$ Edit: I ...
0
votes
1answer
63 views

Factorization of $x^n - x$

While studying about the galois field $GF(2)[x]$, i wanted to find out whether a given polynomial is primitive or not. To do that i need to factor this term: $x^8 - x$. I got the only solution that ...
0
votes
1answer
56 views

A number with greatest amount of factors that are prime and at the same time finding the upper limit of non-composite factors for a number

So we have a number $n$ which is composite and odd at the same time. And task was to prove that all of its prime factors must be at most $\frac{n}{3}$. Second task was to justify how many prime ...
0
votes
1answer
121 views

Fastest way to find all the prime factors of a very large number without calculator? [closed]

Largest possible factor of a very large number n would be number itself. The largest would be n/2 (if prime) if n/2 is not prime then it would be less than n/2 . The smallest factor would be 1. Is ...
-2
votes
1answer
36 views

What does coprime mean in the beal conjecture?

$2^8+2^8=8^3$ How does coprime condition invalidate this solution?
-3
votes
2answers
46 views

Highest power of a number that divides a larger number?

Is the method of prime factorization valid for finding largest power of a number n such that n divides the number x also x>n? E.g:- Question: Highest power of 2 that divides $2^2 * 3^3 * 4^4 * 5^...
5
votes
1answer
91 views

Find all $n$ such that $n/d(n) = p$, a prime, where $d(n)$ is the number of positive divisors of $n$

Let $d(n)$ denote the number of positive divisors of $n$. Find all $n$ such that $n/d(n) = p$, a prime. I tried this, but only I could get two solutions. I proceeded like this - Suppose $$n = p^r \...
0
votes
3answers
37 views

How many positive integers $x \le 3600$ are there such that $\gcd(3600, x)=9$?

I'm trying to answer this question which has a hint: think about $\mathbb Z_{3600}$. I tried to set up a linear equation,$\mod{3600},$ without any success. Not even the factorization of $3600$ gives ...
0
votes
1answer
28 views

Find numbers with n-divisors in a given range

I'm trying to answer this question. Are there positive integers $\le200$ which have exactly 13 positive divisors? What about 14 divisors? If yes, write them. If no, explain why not. Because I'm ...
2
votes
0answers
72 views

Is there any theorem connect to this problem?

It is a question I always ask when I was a primary student: Could a number only contains digit'1' with $p$ digits writes $$A=\frac{10^{p}-1}{9} = \underbrace{11\cdots 1}_{p\text{ digits}}$$ be a ...
2
votes
0answers
41 views

An iteration based on prime factorisation

This is just a curiosity; as far as I know it is of no deep mathematical significance. Consider the function $f : \mathbb Z_{> 0} \to \mathbb Z_{> 0}$ defined by putting $f(1) = 1$, and $$ f\...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
81 views

Integers of this form that pass the Fermat Primality test are prime, proof?

If an integer, $2p + 1$, where $p$ is a prime number, is a divisor of the Mersenne number $2^p - 1$, then $2p + 1$ is a prime number. My argument is that because divisors of the Mersenne number $2^p -...
1
vote
0answers
84 views

Can anything be said about whether an integer has an even or odd number of prime factors?

Because of the odd nature of my question, I am interested in partial solutions if a complete solution is not known. Specifically, the question I am trying to answer is the following: Is there a ...
7
votes
1answer
79 views

On numbers with small $\varphi(n)/n$

Let $\Phi(n) = \varphi(n)/n = \prod_{p|n}(p-1)/p$ be the "normalized totient" of $n$. Some facts: $\Phi(p) = (p-1)/p < 1$ for prime numbers with $\lim_{p\rightarrow \infty}\Phi(p) = 1$ $\Phi(n) = ...
4
votes
2answers
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 ...
8
votes
0answers
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$ ...
2
votes
0answers
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."...
-1
votes
1answer
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 ...
4
votes
2answers
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 ...
0
votes
2answers
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 ...
0
votes
0answers
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++? ...
0
votes
1answer
21 views

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 ...
1
vote
1answer
57 views

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{...