-2
votes
3answers
103 views

An intutive way to think about odd and even numbers. [on hold]

What is an intuitive way to think about odd and even numbers? And about divisibility also...
1
vote
1answer
102 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$. ...
4
votes
1answer
49 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 ...
1
vote
1answer
64 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 ...
4
votes
1answer
70 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 ...
1
vote
1answer
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?
-2
votes
2answers
55 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 ?
2
votes
1answer
63 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 ...
1
vote
1answer
33 views

show that if $m,n\in\mathbb{N}$ are such that $(m,n)=1$, then $\frac{(m+n-1)!}{m!n!}\in\mathbb{N}.$

show that if $m,n\in\mathbb{N}$ are such that $(m,n)=1$, then $$\frac{(m+n-1)!}{m!n!}\in\mathbb{N}.$$ I have a theorem (shown in my text) that says $$\fbox{If $a_1,...,a_m\in\mathbb{N}^*$ then ...
2
votes
1answer
32 views

Find the smallest value of $n$ so that the greater potency of $5$ which divides $n!$ is $5^{84}$. What are the other numbers that enjoy this property?

Find the smallest value of $n$ so that the greater potency of $5$ which divides $n!$ is $5^{84}$. What are the other numbers that enjoy this property? I thought I would put together an equation ...
2
votes
1answer
63 views

Find the prime factor decomposition of $100!$ and determine how many zeros terminates the representation of that number.

Find the prime factor decomposition of $100!$ and determine how many zeros terminates the representation of that number. Actually, I know a way to solve this, but even if it is very large and ...
1
vote
2answers
30 views

If $N$ is not a power of a prime, why does 1 have -1 as a root modulo $N$?

If integer $N$ is not a power of a prime, it is the product of two coprime integer numbers greater than 1. As a consequence of the Chinese remainder theorem, the number 1 has at least four ...
3
votes
1answer
64 views

Finding $a_n$ such that $x^n+a_1x^{n-1}+\cdots+a_{n-1}+a_n$ cannot be factored when $a_1,\cdots,a_{n-1}$ given

Let $n\ge 4\in\mathbb N$. Suppose that $a_1,a_2,\cdots,a_{n-1}$ are given integers. Then, here is my question. Question : Is the following true for any $(a_1,a_2,\cdots,a_{n-1})$ ? There ...
0
votes
1answer
59 views

Computing p and q from private key

We are given n (public modulus) where $n=pq$ and $e$ (encryption exponent) using RSA. Then I was able to crack the private key $d$, using Wieners attack. So now, I have $(n,e,d)$. My question: is ...
1
vote
1answer
81 views

Number of divisors of a number

Is there any trick to find the number of divisors of any number? For e.g., a quick way to tell the number of divisors of 987655432 (chosen randomly)? EDIT: And it has to be done without prime ...
3
votes
0answers
72 views

Symmetry in the Sum of Factors

The factors of 72 are 1,2,3,4,6,8,9,12,18,24,36,72. The factors can be organized as such $$m=1,2,3,4,6,8$$ $$n=72,36,24,18,12,9$$ Knowing the symmetric properties and that the 12 factors exist. Pair ...
3
votes
2answers
166 views

Why does prime factorization hold in the set of integers of the form $4k+1$?

I want to prove that in the set $$ S = \{4k+1 : k\text{ is a positive integer}\}$$ (i.e. $S = \{1, 5, 9, 16, \dots \}$) unique prime factorization holds. How do I do that? Edit: a prime in this ...
2
votes
1answer
74 views

Unexpected data for primes?

I found some unexpected data for primes. Consider $p(n)$ being the product over all primes smaller than or equal to $n$. When factoring $p(n)^a +1$ for $a=1$ or $a=2$ we get the expected amount of ...
1
vote
0answers
60 views

Parametric Equation solving over integers

I have a question on my mind I am trying to solve. However I am stuck at a point. If you could help, I would be very pleased. $$\frac {x_2y_2z_2}{x_2y_2+y_2z_2+x_2z_2}=\frac ...
3
votes
1answer
213 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$$ ...
1
vote
1answer
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?
2
votes
0answers
90 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 ...
1
vote
1answer
217 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 ...
2
votes
2answers
238 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$$ ...
5
votes
1answer
51 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 ...
14
votes
2answers
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 ...
1
vote
4answers
76 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 ...
3
votes
1answer
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 ...
2
votes
1answer
92 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 ...
1
vote
1answer
319 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 ...
1
vote
0answers
45 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 ...
1
vote
0answers
98 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 ...
0
votes
1answer
120 views

Integer Factoring Algorithm Speeds

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

Distinct-degree factorization

I'm trying to understand distinct-degree factorization from Wikipedia. I'm trying the algorithm on paper with $q=9$ and $f(x) = (x+4)(x+5) = x^2+2 \in F_{q}$. We start with $i=1$. I calculate $g = ...
1
vote
1answer
64 views

probability of a number not having factors below n?

I want to know the probability that a number is not divisible by any prime smaller than or equal to n. ie, I find a big number, I trial division it up to 300000 and don't find any factors. I want to ...
3
votes
1answer
133 views

How to implement birthday paradox continuation of elliptic curve factorization algorithm

I have already implemented Lenstra's algorithm for factoring integers using elliptic curves; it is shown below, or you can run it at http://ideone.com/QEDmMY. Beware that my code is optimized for ...
5
votes
0answers
150 views

Fastest Primality test using $N-1$ Factorization?

If $N-1$ could be factored easily with several small prime factors, then what is the fastest way to check $N$ for primality? Updated I'm aware of Pocklington primility test which is not good for ...
5
votes
0answers
148 views

Carmichael number factoring

The task I'm faced with is to implement a poly-time algorithm that finds a nontrivial factor of a Carmichael number. Many resources on the web state that this is easy, however without further ...
4
votes
2answers
178 views

Are Euclid numbers squarefree?

Are Euclid numbers squarefree ? An Euclid number is by definition a Primorial number + 1. See http://mathworld.wolfram.com/Primorial.html. In notation the $n$ th Euclid number is written as $E_n = ...
0
votes
3answers
142 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: ...
0
votes
2answers
171 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 ...
2
votes
0answers
152 views

How many co-primes are there for a big integer N over a specified interval?

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$ ...
8
votes
1answer
2k views

Pollard-Strassen Algorithm

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 ...
3
votes
1answer
233 views

Roots of rational equation with multiple variables?

Let's say we have a rational polynomial in $k$ variables. We are only interested in rational solutions. If $k = 1$, name the variables ${x}$, if $k = 2$, name them ${x,y}$. For $k = 1$, it can be ...
1
vote
2answers
82 views

Does this sequence have this interesting property relating to the prime factorization of the index?

Define a sequence as $a_0 = 0$ and $a_n$ equals the number of divisors of $n$ (including 1 and $n$) that are greater than $a_{n-1}$. This is sequence A152188 in OEIS, by the way. (For example, the ...
0
votes
1answer
249 views

Calculating powers of 2 on a 2D grid without factoring.

Consider the following 2D infinitely large grid where the dots represent infinity: ...
2
votes
2answers
246 views

Determine the number of factors for extremely large numbers.

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them? Even an ...
2
votes
3answers
313 views

Factoring extremely large integers.

The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
1
vote
0answers
136 views

A special factorization

Suppose that monic polynomial $f(x)\in\Bbb Z[x]$ such that for all $m\in\Bbb Z$, $m>1$, there's no integers $\langle r,r_1,\ldots,r_m\rangle$ such that $f(r)=f(r_1)\cdots f(r_m)$. Is there any ...
3
votes
1answer
166 views

Dixon's random squares algorithm: a step in the proof of its subexp. running time

I am currently working to understand Dixon's running time proof of his subexp integer factorization algorithm (random squares). But unfortunately I can not follow him at a certain point in his work. ...