Divisors of N

**mndi1105** · October 27th 2008, 12:17 PM

Show that if a ≥ 3, then an− 1 has at least 2v(n) divisors. (where v(n) is the number of divisors of n)

**NonCommAlg** · October 27th 2008, 03:36 PM

Originally Posted by mndi1105

Show that if $a \geq 3,$ then $a^n - 1$ has at least $2\nu(n)$ divisors. (where $\nu(n)$ is the number of divisors of n)

Let $d \mid n.$ define $A(d)=\{a^d - 1, \ \frac{a^n - 1}{a^d - 1} \}.$ clearly $A(d)$ is a subset of set of divisors of $a^n -1.$ we need a trivial lemma:

Lemma: if $a \geq 3$ and $k \geq 1, \ \ell \geq 1, \ n \geq 1,$ then: $(a^k - 1)(a^{\ell} - 1) \neq a^n - 1.$

Proof: suppose $(a^k - 1)(a^{\ell} - 1) = a^n - 1.$ then we'll get: $a \mid 2. \ \ \ \Box.$

so, since we've assumed that $a \geq 3,$ the above lemma tells us that for any $d \mid n,$ we have $|A(d)|=2$ and if $d_1 \neq d_2,$ then $A(d_1) \cap A(d_2) = \emptyset. \ \ \ \Box$

Thread: Divisors of N

LinkBack

Thread Tools

Display

Divisors of N

Similar Math Help Forum Discussions

Relitivly prime, unique divisors of divisors

divisors

Zero divisors and such

More on Sum of the divisors

divisors

Search Tags