1
vote
1answer
29 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 ...
9
votes
0answers
145 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor ...
10
votes
3answers
174 views

If $a^4+b^4\in\mathbb Q$ and $a^3+b^3\in\mathbb Q$ and $a^2+b^2\in\mathbb Q$, prove that $a+b\in\mathbb Q$ and $ab\in\mathbb Q$.

If $\begin{cases}a^4+b^4\in\mathbb Q\\ a^3+b^3\in\mathbb Q\\ a^2+b^2\in\mathbb Q\end{cases}$, prove that $a+b\in\mathbb Q$ and $ab\in\mathbb Q$. It is given that $a,b\in\mathbb R$. The proof of ...
1
vote
1answer
105 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$. ...
2
votes
4answers
152 views

Determine the largest power of 10 that is a factor of $50!\,$?

How would one find the largest power of 10 which is a factor of $50!\,{}$?
2
votes
0answers
73 views

What is the line of thinking to get $[(n^2+3n+1)^2-5n(n+1)^2]$ from $(n^4+n^3+n^2+n+1)$?

There is this one little tiny step along the working that I don't quite understand, but I think it is better if I write the whole problem and solution for clarity. Problem: Factorise $5^{1995}-1$ ...
1
vote
1answer
34 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
36 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
82 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 ...
0
votes
0answers
36 views

Polynomial factorization over an infinite field - is there an algorithm

In my previous questioned I asked how do I factor a polynomial, and I gave an easy example of a polynomial of degree 2. But now I have another question I need to solve. I need to factor ...
1
vote
1answer
41 views

Specific Annual Examination Marks

Steve has recently got his annual exam result.He has got upper than 690 out of 750.His obtained marks has odd number of factors.What is his obtained marks?
0
votes
1answer
202 views

Why perfect square has odd number of factors

can someone please describe me why only the perfect square has odd number of factors.why does other number not has odd numbers of factors? I understand it but don't find any mathmetical proof.Please ...
0
votes
0answers
281 views

New method derived out of Fermat's factorization method

Let us take two examples: a) $N=943=41*23=(\frac{41+23}{2})^2-(\frac{41-23}{2})^2$ but if we take $B=\frac{N+1}{4}$ then we can represent it as $B={x}^2-({y}^2+y)$ and in our case: ...
1
vote
2answers
52 views

Factorizing a difference of two $n$-th powers

How can be proved that $$a^n-b^n=\displaystyle\prod_{j=1}^{n}(a-\omega^j b)$$ where $\omega=e^{\frac{2\pi i}{n}}$ is a primitive $n$-th root of $1$?
0
votes
0answers
33 views

Greatest Common Divisor of $(m^a - 1)$ & $ (m^b - 1 )$ [duplicate]

Let $a, b, m \in \mathbb Z^+$ with $gcd(a,b) = 1$. Prove that $gcd(m^a - 1, m^b - 1) = m-1$. My method is to show that (1) $gcd(m^a - 1, m^b - 1)$ divides $m-1$ and (2) $m-1$ divides $gcd(m^a - 1, ...
1
vote
1answer
79 views

Greatest common divisor of $n!$ and $ H_n n!$

Let $H_n$ be the $n$th harmonic number, ie. $H_n=1+\frac{1}{2}+\frac{1}{3}+ \cdots+\frac{1}{n} .$ I would like to get the value of $\gcd(n!,H_n n!)$, where $\gcd$ is the greatest common divisor, ie, ...
1
vote
4answers
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 ...
3
votes
1answer
93 views

Find a divisor satisfying a given congruence

Suppose I have a highly composite positive integer $N$ with at least $10^{15}$ divisors for which I know the prime factorization. Given $M$ with $\gcd(M,N)=1$ is there an efficient way to find a ...
1
vote
2answers
457 views

Number of proper divisors generally prime

If we count the number of proper divisors of a positive integer, why do we usually get a prime number (or $1$)? ...
4
votes
1answer
153 views

Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?

The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all? With the ...
2
votes
3answers
3k views

How many positive integers are factors of a given number?

I've been trying to find / generate a formula for the following problem: Given a number, how many positive integers are factors of this number. In practice, you could simply build a table as such ...
5
votes
3answers
97 views

Given $N$, find $ab = N$ with $a$ and $b$ as close as possible

Given a number $N$ I would like to factor it as $N=ab$ where $a$ and $b$ are as close as possible; say when $|b-a|$ is minimal. For certain $N$ this is trivial: when $N$ is prime, a product of two ...
0
votes
2answers
71 views

Transform a positive integer to find its next greatest factor

Suppose I am trying to find factors of a particular positive integer num. Suppose I also have a function findGreatestFactor(num) ...
1
vote
1answer
48 views

factorization of numbers with euclidian approach

Anyone know about this topic?. Factorization of numbers with euclidian approach I searching in the internet, but i couldnt find any source of this topic?. Some one can help me about this topic?. I ...
5
votes
0answers
154 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 ...
2
votes
2answers
176 views

Where did I go wrong on computing the legendre symbol $\left(\frac{150}{1009}\right)$

Where did I go wrong on computing the legendre symbol $\left(\frac{150}{1009}\right)$. I know the answer is $1$. For some reason every way I compute this legendre symbol I get $-1$: ...
1
vote
0answers
77 views

Understanding of Pollard rho factorization

I am trying to better understand the ideas and intuition behind the Pollard Rho factorization algorithms. Given an $x_0$ and an irreducibe polynomial we can create a sequence from the recursive ...
0
votes
3answers
154 views

Pattern in Fermat Factorization

I have the Fermat Factorizations of $n = pq$ where $p$ and $q$ are primes. I am trying to find a formula/pattern for the number of cycles required to perform the factorization in terms of $n, p, q$. ...
1
vote
3answers
73 views

Correctness of Fermat Factorization Proof

I have asked similar questions regarding this proof. But now I would like to know if my reformulation (after perseverance and different thinking) is correct. Prove: An odd integer $n \in \mathbb{N}$ ...
0
votes
1answer
63 views

Correctness of Fermat's Factorization

Is this proof correct: An odd integer $n \in \mathbb{N}$ is composite iff it can be written in the form $n = x^2 - y^2, y+1 < x$ Proof: $\leftarrow$ Want: $n = ab$ Where $a$ and $b$ are odd ...
3
votes
3answers
974 views

Does knowing the totient of a number help factoring it?

Edit: The quoted question addresses only numbers of the form $p^a q^b$, I asked a general question for arbitrary $n$. If $n$ is a prime or a product of 2 primes then knowing its totient ...
5
votes
2answers
330 views

Find all ways to factor a number

An example of what I'm looking for will probably explain the question best. 24 can be written as: 12 · 2 6 · 2 · 2 3 · 2 · 2 · 2 8 · 3 4 · 2 · 3 6 · 4 I'm familiar with finding all the prime ...
6
votes
3answers
312 views

Finding the number of factors of product of numbers

If $a,b,c,d\in\mathbb{N}$ be distinct. Each of which has exactly five factors, can we determine the number of factors of the product of $a,b,c,d$? Edit This is the solution given the in the back of ...
0
votes
2answers
277 views

Factoring for extremely large numbers that are a power of 2.

This is a variation of this question. I want to find the number of factors for a given large integer that I already know to be a power of 2. Given that the number is a power of 2, does that help by ...
4
votes
1answer
123 views

If $A,B$ are factors of $2^6 3^4 5^2,$ how many values of $|A-B|$ are possible?

Let $x=2^6 3^4 5^2$, then how many distinct values of $|A-B|$ are possible where $A, B$ are the factors of $x$? How to approach this problem?
7
votes
1answer
828 views

Even numbers have more factors than odd numbers…

This was an exercise to show that, in a sense, the even numbers have more prime factors than the odds, but--if it's right-- I still have a question. As an heuristic calculation, we could take a large ...
5
votes
1answer
255 views

Finding the radical of an integer

Given a number $x = p_1^{e_1}\cdots p_n^{e_n}$ with different primes $p_i$ and exponents $e_i \ge 1$, is there an efficient way to find $p_1\cdots p_n$? I ask this because for polynomials it's ...
1
vote
0answers
93 views

Is there a name for a number whose factors' exponents are all prime?

For instance, 864, whose factorization is 2^5 x 3^3.
1
vote
1answer
187 views

Unique factorization less than 100

How do I approach this problem using unique factorization?... How many numbers are product of (exactly) $3$ distinct primes $< 100$? edit: Just to add to that, How does unique factorization ...