# Tagged Questions

518 views

### Is 641 the Smallest Factor of any Composite Fermat Number?

Consider the sequence $a_n = 2^{2^n}+1$ of so-called Fermat numbers. It's well known that $a_5$ isn't prime ($a_5 = 641 \cdot 6700417$, this is due to Euler). What I want to know about this sequence ...
80 views

### Factoring numbers

I was given the following problem: Prove that 767, 76767, 7676767 ... are all composite. Making a sequence $a(n)$ = {767, 76767, 7676767, ...} you can show that $a(3k+1)$ is divisble by 13, ...
64 views

39 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 ...
94 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 ...
32 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 ...
66 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 ...
81 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 ...
89 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 ...
87 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 ...
184 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 ...
83 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 ...
65 views

79 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 ...
95 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 ...
339 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 ...
104 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 ...
136 views

### Integer Factoring Algorithm Speeds

Given $N=pq$, would $\frac{p-1}{2}$ steps be fast compared with extant factoring methods?
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 = ... 1answer 65 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 ... 1answer 150 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 ... 0answers 158 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 ... 0answers 162 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 ... 2answers 184 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 = ...
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: ...