# Tagged Questions

**3**

votes

**3**answers

330 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

142 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

118 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

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

**6**

votes

**4**answers

412 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

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

**7**

votes

**2**answers

310 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

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

**6**

votes

**1**answer

357 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) ...

**13**

votes

**1**answer

1k 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

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

**7**

votes

**3**answers

729 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

138 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

**1**answer

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

**16**

votes

**11**answers

2k 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

413 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

504 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$ ...

**1**

vote

**3**answers

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

**11**

votes

**2**answers

677 views

### Saying things rapidly about integer factorisations

Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or ...

**1**

vote

**2**answers

506 views

### find the minimum difference between the factors of a number

Given a number c, what is the smartest way to find |x - y| such that x * y =c and |x - y| is minimum

**1**

vote

**2**answers

364 views

### Finding a divisor of a number under a constraint

Given 2 positive integers $n, l$ with $ l \leq n$, I am looking for a way to find the largest divisor $d$ of $n$, such as $d \leq l$.
Assume $n$ has too many divisors for an exhaustive search.
Thanks ...

**7**

votes

**2**answers

600 views

### Factoring some integer in the given interval

I'm posting this question here (rather than on CSTheory) since it seems to require much more knowledge about number theory than algorithms.
Let N be a positive integer. Is there an efficient (i.e. ...

**5**

votes

**3**answers

1k views

### Reduction from factoring to solving Pell equation

The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims
There are reductions from factoring to solving Pell’s equation, and from solving Pell’s
...

**16**

votes

**1**answer

939 views

### Factoring Integers using Complex Integrals

Suppose $n$ is an integer and we wish to factor it. As a special case we have $n = pq$ with $p,q$ distinct primes. The problem: factoring $n$ via complex analysis tools
Background
I have been ...

**2**

votes

**1**answer

612 views

### What are the chances of finding a small factor?

EDIT 2011.05.09
Thanks to Junkie and Tapio Rajala for checking on me. While most of the candidates
referred to below have small factors, the "large" small factors I list below are incorrect. Also, ...

**2**

votes

**1**answer

641 views

### A subring question (revised)

Hello,
Let $K/{\mathbb Q}$ be a finite extension which is not necessarily Galois, and ${\mathcal O}$ be the ring of integers of $K$. Let $p$ be a prime in ${\mathbb Q}$ and let
$p {\mathcal ...

**7**

votes

**4**answers

1k views

### Consecutive numbers with n prime factors

Let $P(m,n)$ mean that there is a number, $M$, such that starting with $M$ there are $m$ consecutive numbers each having exactly $n$ distinct prime factors. Is it obvious that $P(m,n)$ is true for ...

**14**

votes

**2**answers

1k views

### How divisible is the average integer?

I don't know any number theory, so excuse me if the following notions have names that I'm not using.
For a positive natural number $n\in{\mathbb N}_{\geq 1}$, define $Log(n)\in{\mathbb N}$ to be ...