Stack Exchange Network

Stack Exchange network consists of 174 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.

-1
votes
1answer
57 views

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

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
0answers
27 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
39 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
82 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
34 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
22 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
70 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
39 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
21 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
26 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
79 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
78 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
76 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
95 views

Every natural number $n$ can be written as $n=s-t$ with $\omega(s)=\omega(t)$

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
107 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$ ...
1
vote
0answers
135 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
52 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
95 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 ...
-2
votes
0answers
30 views

Ramifications of being able to factor large composite numbers

I think I found 2 methods of quickly factoring large composite numbers made from multiplying 2 large prime numbers. What are some possible ramifications?
0
votes
2answers
56 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
33 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
19 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
52 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{...
3
votes
2answers
305 views

Countability of Algebraic numbers proving the existence of some equality?

Let $\mathbb{A}$ denote the algebraic numbers. Consider the set of numbers defined as follows: $$S=\{2^{k_0}3^{k_1}5^{k_2}\ldots\;|\;k_0, k_1, k_2\ldots\in\mathbb{Q}\}$$ where $2,3,5\dots$ are the ...
12
votes
1answer
900 views

Are all highly composite numbers even?

A highly composite number is a positive integer with more divisors than any smaller positive integer. Are all highly composite numbers even (excluding 1 of course)? I can't find anything about this ...
0
votes
1answer
51 views

Maximum number of distinct prime factors of numbers below $2^{64}$

What is the maximum number of distinct prime factors of numbers below $2^{64}$? I'm interested in the exact count, not just an estimate. In other words, what is the largest $\omega(n)$, where $n < ...
1
vote
1answer
48 views

Show that any prime divisor of $x^4+x^3+x^2+x+1$, with $x\in\mathbb{N}$, is $5$ or $1$ mod $5$

We can write the "polynomial" as follows: $$x^4+x^3+x^2+x+1=\frac{x^5-1}{x-1}.$$ For even $x=2y$, we have that $x^5-1=(2y)^5-1=32y^5-1\equiv1$ mod $5$. For odd $x=2y+1$, we have that $(2y+1)^5-1\...
0
votes
1answer
29 views

Proving the product of an odd number and the power of 2 is bijective [duplicate]

How do I prove this function is bijective? $$v(s,p)=2^{p-1}(2s-1). $$ The domain is the natural numbers and the codomain is also the natural numbers So I have to somehow show that every natural ...
0
votes
2answers
38 views

Determine the number of positive integers $a$ such that $a\mid 9!$ and gcd $(a, 3600)=180$.

Determine the number of positive integers $a$ such that $a\mid 9!$ and gcd $(a, 3600)=180$. What I know as of now is that $180\mid 9!$ and that $180\le a\le9!$. The prime factorization of 180 is $(...
0
votes
1answer
19 views

Is there a term for numbers whose sum of prime factors are “amicable”

Amicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number. Is there a name for two different numbers who sum of prime factors is ...
4
votes
0answers
27 views

Can I efficiently enumerate all numbers in a range that have a prime factor in another given range?

Suppose $a<b$ are positive integers. The object is to determine all the numbers $x\in [a,b]$ having a prime factor in the range $[c,d]$ efficiently (that is without factoring all the numbers in the ...
0
votes
0answers
35 views

What is known about the prime factorization of numbers of the form $2^k+1$?

Let $n=2^k+1$, $k$ a positive integer. What is known about the prime factorization of these numbers? For example, consider $J(n)=\Omega(n)-\omega(n)$, where $\Omega(n)$ is the sum of multiplicities ...
3
votes
1answer
92 views

Is $k=553276187$ the smallest solution?

I search the smallest positive integer $k$, such that $40!+k$ splits into three primes having $16$ decimal digits. The smallest solution I found is $$k=553\ 276\ 187$$ You can see the factorization ...
2
votes
0answers
49 views

Simplifying radicals without using prime factorization

Is there an easy way to simplify radicals? For example, take the case of $\sqrt{252}$. We can the find prime factorization of $252$ as $252=2\times 2\times 3 \times 3\times 7$ and thus we get $\sqrt{...
1
vote
2answers
77 views

How exactly does wheel factorization work and what is it used for?

I would like to learn how to use wheel factorization but am having trouble understanding it. I tried reading the wikipedia article but found it confusing (even the talk page says it's a mess). What ...
0
votes
1answer
25 views

Prime Factorization for Square Roots with unknowns

I need to help my daughter with math, but I don't understand it myself. We need to solve for $x$ and $y$ in the following equation, using prime factorization: $$\sqrt{1890x} = \sqrt{2100y}$$ Can ...
1
vote
0answers
80 views

What is the smallest solution of $42!+k=P18\cdot P18\cdot P18\ $?

What is the smallest positive integer $k$ , such that $$42!+k$$ splits into three primes with $18$ digits ? My currently best result is $$k=31449145975909$$ http://factordb.com/index.php?query=42%21%...
0
votes
2answers
20 views

Does a function that maps from (almost) any natural number to its set of prime factors is surjective?

Let $A$ be the set of all prime numbers, let $B = \mathbb{N} - \{0,1\}$, and let $f : B \to P(A)$ be the function that maps any $b \in B$ its set of prime factors. e.g, $f(70)=\{2,5,7\}$. Is $f$ ...
0
votes
0answers
65 views

Factors of $2^{3511-1}-1$, where $3511$ is a Wieferich prime.

$\frac{3281273-715031}{2}$ divides $2^{3511-1}-1$, where $3511$ is a Wieferiech prime and $3281273$ and $715031$ are two Sophie Germain primes. Factors of $2^{3511-1}-1$ are $73$,$31$,$3$ and $7$. ...
4
votes
0answers
153 views

Review of proof attempt of Bertrand-Chebyshev Theorem

In the first line of Chapter Three of my graduate level text from which I am working from, the author declares the following divisibility relation to be the basis of Chebyshev theorem, but has also ...
3
votes
1answer
88 views

What is the smallest $k$ , such that $44^{44}+k$ has the desired property?

I search the smallest positive integer $k$, such that $44^{44}+k$ splits into three distinct prime factors each having $25$ decimal digits. The $21$-digit number $k=621725397145122340237$ does the ...
1
vote
0answers
24 views

Characterizing commutative semigroups with a factorization property.

Let $(N, \times)$ be a commutative semigroup and assume that a countably infinite subset $P$ of $N$ algebraically generates $N$, and let ${\mathcal F}(P)$ denote the set of all non-empty finite ...
1
vote
1answer
43 views

I want to know my mistake in the method

Here's the question: Let $N$ be a positive integer, not divisible by $6$. Suppose $N$ has $6$ positive divisors, the number of positive divisors of $9N$ is: I know how approach these questions ...
1
vote
1answer
25 views

Checking if the Product of n Integers is Divisible by Prime N

Given $n$ integers, $x_1, ... , x_n$, is there some well-known procedure or algorithm that checks if the product $x_1 * ... * x_n$ is divisible by some arbitrary prime $N$ using minimal space? Since ...
0
votes
1answer
51 views

Proof verification: finding all prime numbers in the form of $n^3-1, n>1$

Let $p$ be a prime number of the form $p = n ^3 - 1$ for a positive integer $n \geq 2$. Then, factoring the difference of perfect cubes, we obtain $p = (n-1)(n^2 + n + 1)$. Since $p = 1 \cdot p$ as ...
7
votes
1answer
95 views

How can I speed up the search for a special number?

A number $N$ is given. The object is to find the smallest nonnegative integer $k$, such that $N+k$ is the product of three distinct primes, each having the same number of decimal digits. For example,...
0
votes
1answer
57 views

The prime factorization of $15$ when finding the number of solutions to $15=a^{2}+b^{2}$.

Find the number of solutions to $15=a^{2}+b^{2}$. My professor told us to write $15$ in the form $2^{a}p_{1}^{t_{1}}\cdots p_{n}^{t_{n}}q_{1}^{c_{1}}\cdots q_{m}^{c_{m}}$, and if any $t_{i}$ is odd, ...
0
votes
3answers
98 views

Find a prime divisor of the these numbers

Find a prime divisor of a) $2^{49} + 1$ b) $50^{125}-1$ c) $2^{49} -1$ d) $2^{52} +1$ Note that $2^m+1$ is not prime unless $m=2^k$, $2^m-1$ is not a prime unless m is ...
5
votes
1answer
111 views

What other uses are there for Prime numbers? [duplicate]

Simple question out of curiosity... Beside the use of cryptographic safety and prime factorization, what other uses are there for prime numbers? Thank you. Edit: To clarify and not confusing with ...
1
vote
0answers
27 views

Non-Linear Diophantine Equation in Two Variables [duplicate]

How many solutions are there in $\mathbb{N}\times \mathbb{N}$ to the equation $\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{1995}$ ? I could solve till I got to the point where $1995^2$ is equal to the ...