The factorization tag has no wiki summary.

**3**

votes

**1**answer

39 views

### $P_3$-factors for 3-regular, 3-connected cubic graphs

Suppose that $G=(V,E)$ is a simple graph.
We know if $G$ is 3-regular, 3-connected and $|V|=4k$ for some $k\in \mathbb{N}$, then $G$ has a $P_4$-factor.
Question. Let $G=(V,E)$ be 3-regular, ...

**1**

vote

**0**answers

39 views

### Factoring quaternion into three parts [closed]

I am faced with a problem where I have a quaternion which represents rotation and three arbitrary axis about which I can make rotations, thus three unit vectors.
What I would like to know is angles ...

**0**

votes

**1**answer

156 views

### Find all possible rational pairs of a parametric sextic and all cases where it is reducible for either parameter

Find all possible rational solutions pairs $(z,a)$ of the equation
$a^6 + a^4 (-18368 + 9184 z - 2912 z^2) + a^2 (61702144 - 61702144 z + 36814848 z^2 - 10694656 z^3 + 1748992 z^4) - z^2 ...

**41**

votes

**4**answers

1k views

### How did Cole factor $2^{67}-1$ in 1903

I just heard a This American Life episode which recounted the famous anecdote about Frank Nelson Cole factoring $N:=2^{67}-1$ as $193707721 \times 761838257287$. There doesn't seem to be a historical ...

**-2**

votes

**1**answer

129 views

### On odd perfect numbers $N$ given in the Eulerian form $N = {q^k}{n^2}$, Part II

I posted this question on MSE two days ago, but did not receive any responses. I have cross-posted it on MO, hoping it gets more attention here and that it is appropriate for this site.
A positive ...

**1**

vote

**2**answers

187 views

### Algorithm for fast factorization of polynomial over $\mathbb Z$ or over $\mathbb F_p$

I want to fast decompose polynomial over ring of integers (original polynomial has integer coefficients and all of factors have integer coefficients) and also over ring of integers modulo prime ...

**4**

votes

**2**answers

287 views

### Find all possible rational values of a parametric quartic such that it is reducible

Description: Given the following parametric quartic polynomial
$y^4 - 28 z y^3 - 14 (656 - 328 z + 83 z^2) y^2 +
4 z (-20464 + 10232 z + 3409 z^2) y +
91 (62208 - 62208 z + 41504 z^2 - 12976 z^3 ...

**0**

votes

**1**answer

217 views

### Find all possible rational values of the parameter of a parametric cubic such that it is reducible

Description: Given the following parametric cubic polynomials ${E}^{3}
- 15\, {\beta}_{\pm}\, {E}^{2} - 3 \left({71\, {\beta}_{\pm}^{2} + 352\, {\beta}_{\mp}}\right) E
+ 135\, {\beta}_{\pm} ...

**4**

votes

**3**answers

427 views

### $2^n$-1 consisting only of small factors

I've checked the factorization of $2^N - 1$ up through N = 120 for the largest prime factor, and it looks like the largest value of N where $2^N-1$ has a largest prime factor under 2500 is N = 60 ...

**12**

votes

**2**answers

594 views

### Factorization when a factor is partially known

Let's say that I have a very large number of the order ($10^{250+}$) which is composite. I have been given one of its factor partially to a significant amount of digits (say 75+). Then, how can I ...

**0**

votes

**1**answer

68 views

### On a reciprocal of Ostrowski theorem on Newton polytopes and factorization

$\newcommand\KK{\mathbb{K}}$Let $\KK$ be any field and $f\in\KK[x_1,\dotsc,x_n]$ be a polynomial. Its support $S_f$ is the set $\{(e_1,\dotsc, e_n) : x_1^{e_1}\dotsb x_n^{e_n}$ has a nonzero ...

**2**

votes

**1**answer

144 views

### Irreducibility of Faulhaber-like Polynomials over $\mathbb Q[x]$

Motivation: Inspired by the famous Faulhaber polynomials $F_k(N)=\displaystyle\sum_{n=0}^Nn^k,$ I decided to study their alternating versions, $\Phi_k(M)=\displaystyle\sum_{n=0}^M(-1)^nn^k$.
For ...

**4**

votes

**0**answers

220 views

### Analog of Euler's factoring technique

Is there an analog of Euler's Two Squares factoring theorem over polynomial rings $\Bbb Z[x]$ by considering a version for non-negative polynomials?
Euler's two squares factoring states that numbers ...

**6**

votes

**3**answers

385 views

### Irreducible/prime/indivisible elements

in what follows all the rings are commutative, nontrivial, with unit.
Recall the following definitions:
1) $\pi\in A$ is prime if $(\pi)$ is a nonzero prime ideal
2) $\pi\in A$ is irreducible if ...

**2**

votes

**0**answers

100 views

### counting irreducible factors

In How hard is it to compute the number of prime factors of a given integer? a question was asked on computing number of prime factors of an integer.
Suppose we have a polynomial $f(X)\in \Bbb Z[X]$ ...

**1**

vote

**0**answers

100 views

### On reducible polynomials

Let $f(x),g(x)\in\Bbb Z[x]$ with $deg(f)>deg(g)$.
Given an integer $B$, is there any algorithm that runs in $\log^c |B|$ for some fixed $c\in \Bbb R$ to find a $h(x)\in\Bbb Z[x]$ (if one exists) ...

**2**

votes

**1**answer

111 views

### Which nonnegative matrices have exact nonnegative matrix factors of smaller dimensionality?

The nonnegative matrix
$V = \left( \begin{array}{cc}
1 & 1 \\
1 & 1 \end{array} \right)$
has nonnegative matrix factors $W = \left( \begin{array}{c} 1 \\ 1 \end{array} \right)$ and $H = ...

**1**

vote

**0**answers

104 views

### Puzzling CAS-detected factorization by cyclotomic polynomials [closed]

If one factorizes by CAS the expression $$x^{\frac{m(m+1)}{2}}\prod_{k=1}^m(x^k+(\frac{1}{x})^k)$$ a puzzling perfect factorization seems to be possible for all natural values of $m$.
E.g. for ...

**3**

votes

**0**answers

95 views

### More 3-connected cubic graphs with all 2-factors of same cycle type?

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...

**6**

votes

**2**answers

250 views

### Cubic graphs whose 2-factors all have the same cycle type

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...

**3**

votes

**2**answers

355 views

### Degrees of factors of polynomial $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$

I’m facing the problem of factoring polynomials of type $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$ and the degrees of factors seem to be quite special. For example, according to my experimental results ...

**2**

votes

**1**answer

174 views

### Bounded domain matrix factorization

Assume we're trying to find $A\in [-1,1]^{n\times d}, B\in [-1,1]^{m\times d}$, from an observed matrix $C\in [-d,d]^{n\times m}$, where $C=AB^T$.
The goal is to return $\widehat A, \widehat B$ such ...

**4**

votes

**0**answers

91 views

### Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form:
\begin{equation}
A =
\left[\begin{array}{c|c}
...

**0**

votes

**0**answers

79 views

### What algebras does the hidden subgroup problem for finite abelian groups apply to?

Shor's algorithm is said to solve the hidden subgroup problem for finite Abelian groups, of which factoring and the discrete logarithm problem for integers belong to. Apparently the HSP for finite ...

**4**

votes

**3**answers

400 views

### Distinct primitive factorizations over integers of number fields

I am curious about the following.
Let $K$ be a number field. For any $a \in \mathcal{O}_K$ in its ring of integers, let $N(a)$ be zero if there exist elements $b, c \in \mathcal{O}_K \setminus ...

**-6**

votes

**1**answer

172 views

### Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that $P-Q \neq 1$ and $N=P^2-Q^2$ [closed]

Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that:
$P-Q \neq 1$ and $N=P^2-Q^2$
I am assuming that the best known solution to this problem runs at $O(2^{|N|})$.
...

**0**

votes

**1**answer

131 views

### Aurifeuillean factorization with number fields

Basically the question is if number fields can be used
in Aurifeuillean factorization.
Probably this is easy and the answer is "no".
Let $f,g \in \mathbb{Z}[x], a \in \mathbb{N}$.
Let $f(x)$ and ...

**8**

votes

**2**answers

610 views

### runs of consecutive non squarefree integers

This question gained no attention at Math SE.
Call a sequence of $k$ consecutive naturals squary if each one of them is divided by a square > 1. The Chinese Remainder theorem trivially guarantees us ...

**7**

votes

**4**answers

508 views

### Are there any fast algorithms for factoring integers that don't work by searching for smooth numbers?

All of the fast algorithms that I have seen which factor integers work by searching for smooth numbers. Are there any fast algorithms for factoring integers that don't work by searching for smooth ...

**4**

votes

**1**answer

685 views

### The number of distinct prime factors of $n\in\mathbb N$

Let $\omega(n)$ be the number of distinct prime factors of a natural number $n$.
Note that $\omega(n)=0\iff n=1$, and that $\omega(24)=\omega(2^3\cdot 3^1)=2\ (\not = 4)$.
(For more details, you ...

**11**

votes

**0**answers

308 views

### Do the coefficients of these irreducible polynomials always become periodic?

Fix $n\in\mathbb N$ and a starting polynomial (or seed) $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_0a_n\ne0$.
Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = ...

**5**

votes

**1**answer

199 views

### Large gaps between consecutive irreducible polynomials with small heights

For a prime gap of length at least $n$, a trivial upper bound for its first occurrence is $N=n!$ or $N=lcm(2,\dots,n)$. A bit better is $N=p_1\cdots p_n$ where $p_k$ is the $k$th prime, as then ...

**7**

votes

**2**answers

391 views

### Number of ways to write an integer as a product of irreducibles

Is there any way to tell the number of distinct ways to factor $a\in\mathcal{O}_k$ (up to units, of course) when $k$ is not a PID? A simple investigation in $\mathbb{Q}(\sqrt{-5})$ with integer ring ...

**3**

votes

**1**answer

347 views

### Proving conditions on $(r+s)^2 \mid (4r^4+1)$, related to Pell oblongs

While working on another problem (Solving the quartic equation $r^4 + 4r^3s - 6r^2s^2 - 4rs^3 + s^4 = 1$), I came across a question which seems to be of [semi-] independent interest.
Conjecture. If ...

**3**

votes

**0**answers

103 views

### Coim factorization of a morphism in a complete well-powered category

In a complete, cocomplete and well-powered category with zero object consider the canonical factorization of a morphism $f=k\circ \mathrm{Coim}(f)$. Does cocomplete+complete+well-powered guarantee ...

**6**

votes

**1**answer

398 views

### Using the decomposition $641 = 5^4 + 2^4$ to factor $F_5$

The question in the title arises from a problem in Stewart's "Galois Theory, Third Edition" (and possibly elsewhere) which has been bugging me for a few days since reading it:
Problem 19.5 (p. 224) ...

**18**

votes

**1**answer

2k views

### Difficulty of factoring a Gaussian integer (compared to factoring its norm)

Given a Gaussian integer $G=a+ib$, with $gcd(a,b)=1$, a well-known strategy for factoring $G$ is to first compute its norm $N(G)=a^2+b^2$, factor the norm and finally recover the correct generator ...

**5**

votes

**2**answers

157 views

### Collision polynomials

Consider $P_n(x)$ polynomials defined through the recurrence relations
$$P_n(x)=2(1-x)P_{n-1}(x)-(1+x)^2P_{n-2}(x),$$ with $P_0(x)=1$ and $P_1(x)=1-3x$.
In fact, the explicit solution of these ...

**3**

votes

**0**answers

150 views

### Significance behind splitting of (x+y)^7-(x^7+y^7)? [closed]

A quick check via third roots of unity establishes$$(x+y)^7-(x^7+y^7) = 7xy(x+y)(x^2+xy+y^2)^2$$
Some questions:
What is the significance of this factorization?
Does it have any connection to the ...

**7**

votes

**3**answers

788 views

### $\omega(p^n - 1)$ as $n \rightarrow \infty$

Although I am also interested in the number of distinct prime factors (not counting
multiplicity), today I use $\omega(m)$ to denote the number of (positive) prime
factors (with multiplicity) of the ...

**2**

votes

**0**answers

157 views

### Elements of low multiplicative order and computing square roots modulo composites

In "On computing factors of cyclotomic polynomials", Richard P. Brent
gives the identity
$$ 4 \Phi_n(x) = A_n(x)^2 - (-1)^{(n-1)/2} n B_n(x)^2 \qquad (1) $$
where $n$ is odd squarefree and $A_n,B_n$ ...

**0**

votes

**2**answers

250 views

### Generating 3SAT circuit for Integer factorization example

I read somewhere that 3SAT can be used to solve Integer Factorization.
If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given ...

**0**

votes

**1**answer

228 views

### How can an integer be factorized as n*m so that n^m has the highest value. [closed]

Given an integer d, is there a way of finding max(n^m), where d=n*m, except brute-forcing it ?
n and m don't have to be primes.
For example:
The number 12 can be factorized into two factors as: ...

**2**

votes

**1**answer

941 views

### Can infinite polynomials be expressed as a product of its linear factors?

Background:
In the 1700s, Euler solved the Basel Problem, which was to solve $\sum_{n=1}^\infty\frac{1}{n^2}$ in closed-form. Euler showed that it was equal to $\frac{\pi^2}{6}$ by first expressing ...

**2**

votes

**2**answers

255 views

### Factorization of antisymmetric bounded holomorphic functions

A basic principle in complex function theory is that one can split off zeros of holomorphic functions in a similar way as for polynomials: If $f$ is holomorphic near $0$ and $f(0) = 0$, then $f(z) = ...

**16**

votes

**11**answers

3k views

### Fastest way to factor integers < 2^60

I've been running a search for Mordell curves of rank >=8 for about 12 months and have identified approximately 280,000 curves in our archivable range, amongst many millions that aren't.
For this ...

**5**

votes

**0**answers

487 views

### Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at
an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and
$b$ are natural numbers. For example, this set of ...

**2**

votes

**3**answers

519 views

### Groups of Rational Points on Gaussian Circles

Let a gaussian circle $C_R$ be any circle defined by the equation:
$$x^2+y^2 = R, (x,y) \in \mathbb{R}^2$$, where $R$ is the norm of a gaussian integer ($R=a^2+b^2, (a,b) \in \mathbb{Z}^2$). IF $R$ ...

**2**

votes

**3**answers

531 views

### For any prime $p$, is there $C$ such that if $x\ge C$, then all but one integer among $x+1, x+2, \dots, x+p$ has Greatest Prime Factor $> p$

I apologize if this is a naive question about greatest prime factors (gpf). I was thinking about the sequence of integers where $\mathrm{gpf}(x) \le p$ where $p$ is any prime.
Clearly, as $x$ ...

**2**

votes

**3**answers

2k views

### Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...