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

learn more… | top users | synonyms (2)

3
votes
2answers
64 views

Prove That $n(n+1)$ Can Never Be a Square Number by Showing the Atleast One of Exponents in the Prime Power Decomposition Isn't Even

Can someone show me how to prove that when $n>0$, $n(n+1)$ can never be a square number by demonstrating at least one of the exponents in the prime power decomposition is not even? Here's what I ...
0
votes
1answer
12 views

Existence of a Repeating Divisor

I have $n$ integers $a_1, a_2, a_3, .., a_n$ let $X = a_1*a_2*a_3*...*a_n$. I want to know a single integer $F$ such that $F^2$ divides $X$. It is told that there will be atleast one such $X$ and ...
0
votes
0answers
18 views

What is the difference between common components of $f(x,y)$ and common factor of $f(x,y)$?

Let $f(x,y)$ be a polynomial.What is the difference between common components of $f(x,y)$ and common factor of $f(x,y)$?
10
votes
3answers
100 views

Can one factor matrices?

I know that one can factor integers as a product of prime numbers. Is there an analog of it to matrices? Can we define prime matrices such that every matrix is a product of prime matrices? Is there ...
1
vote
1answer
17 views

Prove that $a(x)$ divides $(v(x) - t(x))$

"Let $a(x), b(x) \in \mathbb{R}[x]$, not both the zero polynomial and suppose that gcd[$a(x), b(x)$] = 1. Let $u(x), v(x) \in \mathbb{R}[x]$ be such that $a(x)u(x) + b(x)v(x) = 1$ Let also $s(x)t(x) ...
0
votes
2answers
16 views

Prove that $q(x)$ does not divide $p_k(x)$

Let $n \in \mathbb{N}$ and let $p_1(x), p_2(x), ... *p_n(x)$ be $n$ irreducible polynomials over $\mathbb{R}$. Define the polynomial $p(x) = p_1(x) * p_2(x) *... *p_n(x) + 1 $ where 1 is the constant ...
1
vote
1answer
49 views

Why does this method for finding the number of factors for number X not work?

As you may know, in order to find the number of factors for natural number X, we take the prime factorization, add one to each exponent, and multiply, as such. $...
4
votes
1answer
40 views

When is the norm of a number even?

In the ring $$\textbf{Z}[i],$$ if the norm of an element is divisible by $2$, then the element must be divisible by $$1 + i,$$ and vice versa. A similar result holds for $$\textbf{Z}[\sqrt 3]$$ and ...
2
votes
1answer
114 views

“Practical” Sieve of Eratosthenes from “Primes Numbers - A Computational Perspective”

Consider the following pseudocode for the Sieve of Eratosthenes, giving us the primes up to $N$: 1) List the numbers $2$ to $N$. 2) Let $p=2$. 2) Cross out $p^2$, then cross out $(p+1)p, (p+2)p, (...
0
votes
0answers
30 views

Prime factors polynomials

I have proved a theorem which I will state: For $f(x)=x^n+\sum_{i=1}^nh_ix^{n-i}$ a polynomial of degree $n$ where $h_i=r_i+d_i$ with $r_i$ real and $d_i$ infinitesimal. Then if $x^n+\sum_{i=1}^nr_ix^{...
2
votes
4answers
153 views

Solutions to a quadratic diophantine equation $x^2 + xy + y^2 = 3r^2$.

Let $k,i,r \in\Bbb Z$, $r$ constant. How to compute the number of solutions to $3(k^2+ki+i^2)=r^2$, perhaps by generating all of them?
2
votes
1answer
72 views

Finding 8 co-primes $\le 2^n$

We can find 8 co-prime integers $\le 2^n$ for sufficiently large $n$. I'm looking for asymptotic bounds for the minimum distance away from $2^n$ we have to go before finding 8 co-primes. In other ...
1
vote
1answer
35 views

Modified Sum of Products

A given number k is to be expressed as a sum of products of integers keeping in mind that the integers used in above process do not exceed their cumulative sum as 100. For e.g., k = 19 can be ...
3
votes
3answers
58 views

What is the sum of the prime factors of $2^{16}-1$?

I know $2^{10}=1024$ and $2^6=64$, but it seems they are not very helpful in solving this problem. There must be a trick to solve the problem in an easy way. What is the sum of the prime factors ...
1
vote
0answers
27 views

Prove by contradiction that : There are Infinite Primes. [closed]

Specify $P$, ~$P$,Q and ~$Q$; For this proof I am having difficulty understanding what p and q signify. I was reading Euclid proof http://www.math.utah.edu/~pa/math/q2.html . But I do not quite ...
2
votes
2answers
64 views

What is the Least Prime Factor of $3^{3241} + 8^{2433}$

I'm not sure how to do this question Attempt $$3^{3241} + 8^{2433}$$ I start by taking this number mod 3 $$3^{3241} + 8^{2433} \equiv 8^{2433} \mod 3$$ No we can see that $8^2 \equiv 1 \mod 3$. So $$...
1
vote
1answer
19 views

Best known inequality for the larger prime number of a product?

We all know given two prime number's $b$ and $a$ whose product is $c$: $$ c \geq b \geq \sqrt c \geq a \geq 2 $$ where, $ab=c$ I was wondering if the inequality for $b$ could be improved upon ...
1
vote
0answers
21 views

Analog of Euler's Factorization method

One of Euler's discoveries was if an integer $n$ can be represented as a sum of two squares in two distinct ways, then one can factor $n$ explicitly. Of course, the method was ineffective as an ...
12
votes
0answers
173 views

Have I discovered an analytic function allowing quick factorization?

So I have this apparently smooth, parametrized function: The function has a single parameter $ m $ and approaches infinity at every $x$ that divides $m$. It is then defined for real $x$ apart ...
2
votes
2answers
106 views

Numbers $m = pq^4$ ($p,q$ are distinct primes) for which $m$ divided by the number of its factors is an integer

The $\operatorname{Ionof}$ (Integer on number of factors) of an integer is the integer divided by the number of factors it has. For example, $18$ has $6$ factors so $\operatorname{Ionof}(18) = \frac{...
1
vote
1answer
27 views

Proving that if gcd(m, n) = 1, and if d divides mn, then there exist unique numbers a and b such that a divides m, b divides n, and d = ab.

What do I know? If d | mn, there exist an integer k such that dk = mn. I also know that because gcd(m, n) = 1 there exist some integers x and y such that mx + ny = 1. I am having trouble to prove ...
0
votes
0answers
13 views

On factoring given $PQ-1$ has small factors.

Suppose we have an RSA number $PQ$ where $PQ-1$ has small factors. Will this give any advantage to factor $PQ$?
2
votes
3answers
190 views

Find the number of even factors of 126000

What is an easy way to solve the problem? I can solve it by trying all possible even numbers, but I don't think it is a smart way. Find the number of even factors of 126000.
4
votes
1answer
37 views

On factoring and integer given the value of its Euler's totient function.

In an entrance test for admission into an undergraduate course in mathematics the following question was asked. Consider the number $110179$ this number can be expressed as a product of two distinct ...
1
vote
0answers
8 views

$\gcd({p_1}^{n_1},{p_2}^{n_2})$ associates with $1$ if $p_1,p_2$ are prime and do not associate

$R$ is a integral domain, $p_1$ and $p_2$ are prime, $p_1$ and $p_2$ do not associate, $n_1,n_2 \ge 1,n_1,n_2 \in \mathbb N $, I need to show that $g:=\gcd({p_1}^{n_1},{p_2}^{n_2})$ associates with $1$...
0
votes
0answers
22 views

best way to find sum of powers of prime factors of a number

What is the best way to find the sum of powers of prime factors of a number? What I did till now is : ...
4
votes
1answer
63 views

Sequence generated by $2^k-1$ contains new prime factors

I was playing around with the sequence where the $k^{th}$ number is equal to $2^k-1$. It seems that all numbers except $63$ contain at least one new prime in there prime factorization. That is a prime ...
3
votes
2answers
53 views

Factoring the factorials

Just for the fun of it, I've started factoring $n!$ into its prime divisors, and this is what I got for $2\leq n\leq20$: $$\begin{align} 2! &= 2^\color{red}{1} &S_e=1\\ 3! &= 2^\color{red}...
0
votes
0answers
67 views

What are the prime factors of $4^{256}+253\ $?

I search a composite number near $4^{4^4}$ with a very large smallest prime factor. A candidate is $$4^{4^4}+253=4^{256}+253$$ The number is composite and has $155$ digits, so it is in the range , ...
2
votes
1answer
55 views

Large Prime numbers

Say we have $2^{690} + 345^4$ and we want to figure out whether this is a prime number. I feel that we could break down the numbers into their respective prime factors (prime factorization) and use ...
0
votes
1answer
47 views

Use Fermat factorization to factor $809009\ldots$

Use Fermat factorization to factor $809009\ldots$ So far I have: \begin{align} \sqrt{809009} & = 889.449 \\ & = 890 \\[6pt] \sqrt{890^2 - 809009} & = 130\ldots ∉ \mathbb Z \\[6pt] \sqrt{...
7
votes
0answers
80 views

Which prime factors of $8^{8^8}+1$ are known?

We have the partial factorization $$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$ The first factor is $F_{24}$. It is composite, but no prime factor is known. A prime factor of the ...
0
votes
2answers
27 views

Let $n = 2^{31}*3^{19}$. Find the number of positive divisors $d$ of $n^2$ such that $1\leq d\leq n$ and $d \nmid n$

Let $n=2^{31}*3^{19}$. Find the number of positive divisors $d$ of $n^2$ such that $1\leq d\leq n$ and $d$ does not divide $n$. My attempt $n^2 = 2^{62} * 3^{38}$ Total divisors $= 1 + 62 + 38 + 62*...
1
vote
1answer
67 views

Factoring semiprimes cost estimation

I have two problems that are the following. The first problem is the following: I need to estimate the cost of factorizing a given semiprime based on previous estimations. For example I have the time ...
0
votes
1answer
25 views

Pollard's $p-1$ method

I've been reading some notes regarding the Pollard's $p-1$ method1 and I came across an aglorithm that (from the math standpoint) I don't fully understand: Given that $\textbf{a = 2}$ and also in my ...
0
votes
1answer
26 views

Calculate Euler inverse function

Given $n$ find all values n such that: $\phi(n) = 26$. I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point. I'll be ...
0
votes
1answer
14 views

Significance of derivative in finding square free decomposition

If $gcd(f(x),`f(x))=1$ then f(x) is square free. But what is the reason behind taking derivative of f(x)? How one came to this conclusion?
0
votes
0answers
26 views

Is this algorithm for testing whether or not an integer is prime correct?

Suppose I want to determine whether or not integer $p$ is prime. I create a cycle graph with $p$ vertices ($C_p$). I take the edge-complement of this graph, which will be the complete graph ($K_p$) ...
2
votes
0answers
45 views

A question on polynomials.

Let a polynomial $f\in\mathbb{R}[x,y]$, and $f(x,y)=(x^2+y^2)p(x,y)^2-q(x,y)^2$ and $p,q$ are coprime to each other. When do, $f$ and $\frac{{\partial f}}{{\partial x}}$ and $\frac{{\partial f}}{{\...
1
vote
2answers
54 views

Proving the set of prime numbers in $\mathbb{Z+}$ is infinite

I'm trying to prove that for any $N \in \mathbb{Z^+}$, there exists only finite many integers $n$ with $\varphi(n) = N$ (i.e. finite amount of numbers that have $N$ numbers relatively prime to them) ...
2
votes
1answer
29 views

Why are primes of the form p^2 - 2 for prime p seemingly unusually likely to be factors of prime-exponent Mersenne numbers?

The sequence A049002 (primes of form $q^2 - 2$, where $q$ is prime) appears to contain a high proportion of elements that are factors of prime-exponent Mersenne numbers (see below). I wonder why? ...
0
votes
0answers
27 views

Prime Decomposition of an ideal in a number field.

I have been stuck on the 26th problem of the 3rd chapter from Marcus' Number Fields. Let $\alpha=\sqrt[3]{m}$ where $m$ is a cubefree integer, $K=\mathbb{Q}[\alpha]$, $R=\mathbb{A} \cap \mathbb{Q}[\...
0
votes
0answers
54 views

Why does this equation has not any solution?

Suppose $P(x,y)$ and $Q(x,y)$ are polynomials, and $P,Q$ are coprime. Why does the equation $${\left( {\frac{{xP + {{\left( {\frac{Q}{P}} \right)}^2}{P_x}}}{{yP + {{\left( {\frac{Q}{P}} \right)}^2}{...
1
vote
0answers
14 views

Integer Logic - Prime and Unique Factorization Proof

I could use some help with this problem: Let a, b ∈ Z (integer set) such that (a, b) = 1. Suppose that ab = $x^2$ for some x in Z (integer set). Prove that a = $y^2$ and b = $z^2$ for some y ...
3
votes
2answers
35 views

Proof of (n) and (n+1) Sharing No Prime Factors

A number $(n)$ has a set of prime factors $\{\alpha_1, \alpha_2,...\alpha_\epsilon\}$ and a number $(n+1)$ has a set of prime factors $\{\beta_1,\beta_2,...\beta_\psi\}$. The conjunction, $\{\alpha_1,\...
0
votes
0answers
24 views

Factorising into Gaussian primes $4+3i$

I want to find the Gaussian prime factors of $(4+3i)$ $$(4+3i)(4-3i) = 25=5^2$$ $$5: (2-i)(2+i)$$ so $$(4+3i)(4-3i) = 25=5^2 = (2-i)(2+i)(2-i)(2+i)$$ That was my answer but the solution says: $$(...
3
votes
3answers
43 views

Proof that $\sum_{d|m} |\mu(d)|=2^n$, where $n$ is the number of distinct prime divisors of $m$?

Given an integer $m$ such that $n$ is denoting the distinct prime divisors of $m$, is there a proof that the sum over the divisors of m of the absolute value of the Möbius function $\mu(d)$ is equal ...
1
vote
3answers
32 views

How to prove that the g.c.d is equal to the prime factorization raised to the minimum of two powers

for the prime factorization of $a$ and $b$ as $$a = p_1^{\alpha_1}p_2^{\alpha_2}\cdots{p_t}^{\alpha_t}$$ and $$b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_s^{\beta_s}.$$ I want to prove that $d = (a,b)$ ...
1
vote
1answer
51 views

How many numbers $m$ satisfy $1 ≤ m ≤ n$ and $\gcd (m, n) = 1$?

Let $n = p^2 q$ where $p$ and $q$ are distinct prime numbers. How many numbers $m$ satisfy $1 \leq m \leq n$ and $\gcd (m, n) = 1$? Note that $\gcd (m, n)$ is the greatest common divisor of $m$ and $n$...
0
votes
0answers
19 views

Exponent of x in the prime factorization of y?

This is a simple one. I recently came across the following phrase: "$(x)_y =$ the exponent of $p_y$ in the prime factorization of $x$, for some $x, y<0$" I know what prime factorization is, and ...