Let $p$ be a prime integer and $n\geq 3$ be a natural number such that $p^n-1$ has a primitive prime divisor. Also let $n=\lambda_1+\cdots+\lambda_m$ such that $n>\lambda_i\geq 1$ for all $i$. I want to show that $(p^{\lambda_1}-1)\cdots(p^{\lambda_m}-1)$ does not divide $p^n-1$.
This is my suggested argument for proving the statement when $p>2$:
Both of $(p^{\lambda_1}-1)\cdots(p^{\lambda_m}-1)$ and $p^n-1$ are polynomials in $p$ with the same degree. If $(p^{\lambda_1}-1)\cdots(p^{\lambda_m}-1)\mid p^n-1$, we then have $p^n-1=c(p^{\lambda_1}-1)\cdots(p^{\lambda_m}-1)$, where $c\in \mathbb{N}$. Since $p>2$, $p^{\lambda_i}-1>1$ for all $i$. Therefore, the coefficient of $p^{\lambda_1+...+\lambda_m}=p^n$ in the expansion of the product $\prod_{i=1}^{m}{(p^{\lambda_i}-1)}$ is 1. Also the coefficient of $p^n$ in $p^n-1$ is $1$, and so we must have $c=1$ . Therefore $p^n-1=(p^{\lambda_1}-1)\cdots(p^{\lambda_m}-1)$. Now if we consider $q$ to be primitive prime divisor of $p^n-1$, then $q$ does not divide $(p^{\lambda_1}-1)\cdots(p^{\lambda_m}-1)$, which is a contradiction. So if $p>2$, it is impossible for $(p^{\lambda_1}-1)\cdots(p^{\lambda_m}-1)$ to divide $p^n-1$.
But as it was discussed in comments, it seems that my argument is not true.
Question 1: Does my argument work? If not, is there any possible way to prove the statement for $p>2$?
The remaining case is when $p=2$. According to the example mentioned in comments $(2-1)(2^2-1)(2^3-1) \mid 2^6-1$.
Question 2: Is there any example of a pair $(n, p)\neq(6,2)$ and a partition $\lambda=(1\leq\lambda_1\leq...\leq\lambda_m<n)$ of $n$ such that $p^n-1$ has a primitive prime divisor and $(p^{\lambda_1}-1)\cdots(p^{\lambda_m}-1) \mid p^n-1$? (Update: There are plenty of such pairs when $p=2$, see comments of Nate below).
I would be grateful for any help.
Asked
Active
Viewed 221 times
2
Math_Student
- 123
- 5
-
2Have you tried when all $\lambda_i$'s are $1$? – Batominovski Aug 15 '16 at 14:26
-
What is special about the case when all $\lambda_i=1$? I still can't see whether $(p-1)^n$ divides $p^n-1$ or not... – Math_Student Aug 15 '16 at 14:34
-
1It is not a special case. If you want to know whether the answer to your question is 'yes' or 'no,' it may be a useful first step to try out trivial cases. – Batominovski Aug 15 '16 at 14:39
-
@Batominovski That's right! If $(p-1)^n \mid p^n-1$, then we have $p^n-1=c \Sigma_{i=0}^{n}{(-1)^i \binom{n}{k}p^{n-k}}$, where $c – Math_Student Aug 15 '16 at 15:07
-
@Batominovski Can we extend this argument to the general case where $p^n-1$ has a primitive prime divisor? – Math_Student Aug 15 '16 at 15:35
3 Answers
2
This is not true in general. Take $p=5$ and $n=3$. Then $\frac{(5^3-1)}{(5-1)^3}=\frac{31}{16}$.
Pax
- 5,682
- 3
- 23
- 50
-
Thank you. But I want to prove that it does not occur in general. – Math_Student Aug 15 '16 at 15:11
-
This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - [From Review](/review/low-quality-posts/669176) – naslundx Aug 15 '16 at 15:17
-
@naslundx I was answering the original form of the question, where the opposite question is asked in less generality. – Pax Aug 17 '16 at 13:44
-
1
It doesn't happen in general, but... $(2^1-1)(2^2-1)(2^3-1) \vert (2^6-1)$
Nate
- 10,746
- 2
- 18
- 33
-
What do you mean by "in general"? Does the divisibility happen if we choose $n$ to be a perfect number and $\lambda_i$'s be proper divisors of $n$ (as your example)? – Math_Student Aug 15 '16 at 16:04
-
I just meant that it is not true that $(p^\lambda_1-1) \dots (p^\lambda_m-1) | (p^n-1)$ for all choices of $p$, $n$, and $\lambda_i$ as in the problem, but that here is an example where it does hold. – Nate Aug 15 '16 at 19:02
-
1I'll also note that for $p=2$ you can find lots of examples by including a bunch of terms where $\lambda_i = 1$, since multiplying by $1$ won't change divisibility. – Nate Aug 15 '16 at 19:05
-
Thank you. That's right. What about the case $p>2$? Is my argument for $p>2$ correct? – Math_Student Aug 15 '16 at 19:17
-
1No, I don't think your solution is correct. You seem to be conflating the notions of a polynomial dividing another polynomial, and a number dividing another number. Given two polynomials $f(x)$ and $g(x)$ with integer coefficients, it is perfectly possible for $f(n)$ to divide $g(n)$ at some values of $n$ even if $f(x)$ does not divide $g(x)$ as polynomials. – Nate Aug 15 '16 at 19:32
-
1
-
1That's right. By the way, all of your examples are contained in the pairs $(n, p)$ such that $p^n-1$ does NOT have any primitive prime divisor. So is possible to prove the non-divisibility for the cases that primitive prime divisors exist? – Math_Student Aug 15 '16 at 19:44
0
Hint: you can also prove that $gcd(p^a-1, p^b-1) = p^{gcd(a,b)}-1$ like in this question.
Quang Hoang
- 15,744
- 24
- 42
-
Would you please explain more about the relation of your hint to the question? As far as I understood, the fact in your hint implies that $\lambda_i \mid n$ for all $i$. – Math_Student Aug 15 '16 at 16:00