# Tagged Questions

330 views

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 ... 1answer 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|})$. ... 1answer 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 ... 2answers 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 ... 4answers 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 ... 1answer 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 ... 2answers 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 ... 1answer 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 ... 1answer 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) ... 1answer 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 ... 2answers 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 ... 3answers 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 ... 0answers 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$... 1answer 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 ... 11answers 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 ... 0answers 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 ... 3answers 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$... 3answers 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$... 3answers 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 ... 2answers 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 ... 2answers 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 2answers 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 ... 2answers 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. ... 3answers 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 ... 1answer 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 ... 1answer 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, ... 1answer 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 ...
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 ...
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 ...