# Tagged Questions

20 views

### Finding coefficients of the min polynomial of an $n\times n$

Given an $n\times n$ matrix, for ease assume this matrix is over the $F_m$. What we know about min poly is the the non-zero components of the min polynomial for this case, ie if there is $x^2$, or ...
40 views

### Factorising after adding a square

I have been thinking about it for quite some time but am unable to find an answer. Let $a,b,c,d,e$ be any distinct natural numbers. Will the relation : $(x-a)(x-b)+c^2=(x-d)(x-e)$ ever hold? I am ...
30 views

### Any simpler way to do Pollard's p-1 method?

I found calculating factorization by Pollard's p-1 method is almost impossible if use a conventional scientific calculator. For example, I am trying to factor ...
105 views

### Is 292229292292 the longest 29-smooth number made of 2's and 9's?

Is 292229292292 the longest 29-smooth number made of 2's and 9's? The factorization is $2^2 7^8*19*23*29$. Is there a general way to find other numbers of this sort without resorting to brute force ...
84 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 ...
16 views

### Find subset of rows whose entries sum to an even number in each column

I am trying to implement Fermat factorization with factor bases. The textbook suggests using row-reduction to find a linearly dependent set of rows. How does one go about finding such a linearly ...
44 views

### Efficient factorization of numbers with unique prime factors

I need a factorization algorithm for numbers of the form $n = p_{1}p_{2}\cdots p_{k}$ with $p_i \neq p_j$ for $i \neq j$ and $p_j \in \{p : p \mbox{ is a prime and } p \leq P_s\}$, where $P_s$ is the ...
131 views

### An intutive way to think about odd and even numbers. [closed]

What is an intuitive way to think about odd and even numbers? And about divisibility also...
106 views

### Sums and differences of distinct factors

Given $k, n \in \mathbb{N}$, let $\tau_{k}(n)$ denote the $k$th positive factor of $n$ in strictly increasing order. For example, $\tau_{1}(6) = 1; \tau_{2}(6) = 2; \tau_{3}(6) = 3; \tau_{4}(6) = 6$. ...
50 views

### Complexity of factoring non-squarefree numbers

Consider the two numbers $N_1=p_1\cdot p_2$ and $N_2=p_1^2\cdot p_2$, where $p_1$ and $p_2$ are primes. Is there any factoring algorithm that can factor $N_2$ faster than the asymptotically fastest ...
87 views

### If discriminant of f is a perfect square, then we can factor f into linear factors

Let $f$ be a binary quadratic form with integer coeficients, $f(x,y)=ax^2+bxy+cy^2$. I'm trying to prove that if $d=b^2-4ac$ is a perfect square $d=k^2$, then we can factor ...
79 views

### Which positive integers can be written in the following form?

I was investigating a generalisation of this problem and found that it reduced to finding where the expression $$\frac{p(p+2m+1)}{2}$$ is an integer, where $p\ge 2$ and $m \ge 0$. Since exactly one of ...
33 views

### Factors of $x^n+1$ over $\mathbb{Z}[x]$

Is there any equivalent to $x^n-1 = \prod\limits_{d|n} \phi_d$ where $\phi_d$ is the $d$th cyclotomic polynomial but for $x^n+1$? Even better, can we generalize any further?
59 views

### Common divisor of natural number sequence [closed]

For all natural numbers $n$, the products $(n+2)(n+3)(2n+5)$ will always share what common divisor ?
70 views

### How many integral solutions of $a,\ b,\ c$ are there such that $2^a \cdot 3^b + 9 = c^2$

How many integral solutions of $a,\ b,\ c$ are there such that $$2^a \cdot 3^b + 9 = c^2.$$ we can get that $$2^a \cdot3^b = (c-3)(c+3)$$ we can make cases if $b \ge 2$ then $c=3k$ then ...
34 views

238 views

### Solve $x+y+z = x^3 + y^3 + z^3 = 8$ in $\mathbb{Z}$

Solve $x+y+z = x^3 + y^3 + z^3 = 8$ in $\mathbb{Z}$ First I tried to transform this equation, substituting $x = 8-y-z$. So I end up with: $$x^3 + y^3 + z^3 = 8$$ $$(8-y-z)^3 + y^3 + z^3 = 8$$ ...
84 views

### How many divisors of $n$ are less than or equal to $m$?

Can I calc it in less than $O(\sqrt{n})$ time?
96 views

### Quadratic Diophantine Equations in Polynomial Time

Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law: $F(x_1, x_2... x_n) = 0$ such that $F(x_1, x_2... x_n)$ is a second degree polynomial It is ...
274 views

### Patterns in $GF(2)$ Polynomial division.

I am testing Prime polynomials in $GF(2)$ and have noticed a pattern that I hope will help. There's a calculator here if you want to familiarise yourself with polynomials over $GF(2)$. I am testing ...
293 views

### Primality test square root of n

I was reading about primality test and at the wikipedia page it said that we just have to test the divisors of $n$ from $2$ to $\sqrt n$, but look at this number: $$7551935939 = 35099 \cdot 215161$$ ...
55 views

### Balanced factors

A non-square number cannot be factored to two identical factors. However, not all non-squares are equal: some of them can be factored to relatively close factors (for example, $6=2*3$), while others ...
158 views

### Simplifying $\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$

How do I simplify: $$\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$$ Should I use modulos or should I factor them? Or any I suppose to use combinatorics? Any one have a ...
77 views

### I cannot find the last factor of this expression?

I'm supposed to factor $x^8-y^8$ (the exponents are 8 for both if it is too difficult to see) as completely as possible. It is easy to factor this to $(x+y)(x-y)(x^2+y^2)(x^4+y^4)$. However, the book ...
45 views

### Factors of non-square

How do you solve to find how many of the positive factors of a number, say 36,000,000, are not perfect square? I know how to do this manually, which took me forever, but I want to be able to solve ...
94 views

### Is there any known algorithm for factoring the fractional components of a binomial?

For a binomial such as $\binom {15} {6}=\frac{15\times14\times13\times12\times11\times10}{6\times5\times4\times3\times2\times1}$, it seems that it always divides evenly into an integer, and I ...
332 views

### Let $N$ = $11^2 \times 13^4 \times 17^6$. How many positive factors of $N^2$ are less than $N$ but not a factor of $N$?

Let $N$ = $11^2 \times 13^4 \times 17^6$. How many positive factors of $N^2$ are less than $N$ but not a factor of $N$? $Approach$: $N$=$11^2$.$13^4$.$17^6$ $N^2$=$11^4$.$13^8$.$17^{12}$ This ...
51 views

### Integer factorization using discrete logarithms

I'm reading up on RSA and attacks on it. At the end of one section of the notes, it asks (without giving an answer) whether or not integer factorization is easy given an oracle which computes discrete ...
101 views

### Prime factors of a random number

Let $r$ be a uniformly random integer between $1$ and $N$, for some large enough $N$ (i.e., I'm only interested in the asymptotics). What is the expected largest prime factor of $r$? Is there a good ...
132 views

### Integer Factoring Algorithm Speeds

Given $N=pq$, would $\frac{p-1}{2}$ steps be fast compared with extant factoring methods?
32 views

148 views

### Reducible polynomial + integer = Reducible polynomial?

Reducible polynomial + integer = Reducible polynomial ? As the title says. More specific : For every integer $n$, does there exist a pair of polynomials $p(x)$ and $q(x)$ such that: ...
179 views

### Finding total number of divisors which divide 2 given numbers [duplicate]

Possible Duplicate: Number of common divisors between two given numbers I need to find the total number of divisors which divide both the numbers lets say N and M. Actually I tried to think ...
How many co-primes are there for a big integer $N$ over a specified interval ? bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ ...
I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all ...