Author |
Topic: factorable if m is odd (Read 1506 times) |
|
Christine
Full Member
Posts: 159
|
|
factorable if m is odd
« on: Jan 17th, 2014, 4:20pm » |
Quote Modify
|
How to prove that n^a + n^(a-1) + n^m + 1 is never factorable if m is even but is always factorable if m is odd
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: factorable if m is odd
« Reply #1 on: Jan 18th, 2014, 1:07am » |
Quote Modify
|
If m is odd, your expression is divisible by n+1. This is trivial if m=1; beyond that, induction works. Increasing m by 2 corresponds to adding nm+2 - nm to the polynomial, which factors as (n+1)(n-1)nm, so divisibility by n+1 is preserved. It leads to na + na-1 + nm + 1 = (n + 1) (na-1 + nm-1 - nm-2 + ... - n + 1).
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: factorable if m is odd
« Reply #2 on: Jan 21st, 2014, 1:26pm » |
Quote Modify
|
If m is even prove by contradiction that n^m + 1 is not divisible by n + 1. If it does there exists a polynomial p(n) such that n^m + 1 = (n + 1)p(n) which must be true for any n. However, if n = -1 the right hand side becomes 0 while the left hand side becomes 2. 2 = 0 is a contradiction.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: factorable if m is odd
« Reply #3 on: Jan 21st, 2014, 1:52pm » |
Quote Modify
|
on Jan 21st, 2014, 1:26pm, rloginunix wrote:If m is even prove by contradiction that n^m + 1 is not divisible by n + 1. If it does there exists a polynomial p(n) such that n^m + 1 = (n + 1)p(n) which must be true for any n. However, if n = -1 the right hand side becomes 0 while the left hand side becomes 2. 2 = 0 is a contradiction. |
| It is, indeed, obvious that n+1 is not a factor if m is even, but we are asked to show that the polynomial does not factor at all.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: factorable if m is odd
« Reply #4 on: Jan 22nd, 2014, 7:58am » |
Quote Modify
|
If a>m and a is odd, then the polynomial will be large and negative when n is large and negative, but large and positive when n is large and positive, so for specific values of a and m, there will always be at least one factor. If, instead, the question asks for a factor that's valid for a given m whatever value a takes, then whatever it is must (unless it's a function of a) be a factor of na+na-1-n-1 (the difference between the polynomials for a given value of a and for a=1). The only two candidate factors are (n+1) and (n-1), which would give roots of n=-1 and n=1 respectively. When n=1, the polynomial always equals 4, so (n-1) is not a root; when n=-1, the polynomial equals 2 for even m and 0 for odd m. The only linear factor of the polynomial, independent of a, for given m and variable a is (n+1), and only for odd m. It's still to show whether there can be factorisations where all factors are functions of a.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: factorable if m is odd
« Reply #5 on: Jan 22nd, 2014, 10:35am » |
Quote Modify
|
My understanding is that we're looking for pa,m(n) = qa,m(n) ra,m(n), where p is the expression given in the original post and q and r are polynomials with integer coefficients. The question is for which a and m such a factorization exists; the factorizations for different a and m do not need to be related in any way.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: factorable if m is odd
« Reply #6 on: Jan 22nd, 2014, 10:59am » |
Quote Modify
|
My plan was to rearrange the expression into two terms: n^a + n^(a - 1) = (n + 1)n^(a - 1) and (n^m + 1) and prove that they have no common factors. By contradiction we've proved that (n^m + 1) is not divisible by (n + 1). We now have to analyze if (n^m + 1 ) is divisible by n^(a - 1). I take it that n, m and a are whole numbers, m is even.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: factorable if m is odd
« Reply #7 on: Jan 22nd, 2014, 12:49pm » |
Quote Modify
|
on Jan 22nd, 2014, 10:59am, rloginunix wrote:My plan was to rearrange the expression into two terms: n^a + n^(a - 1) = (n + 1)n^(a - 1) and (n^m + 1) and prove that they have no common factors. |
| I'm not sure how that would help. For example, n2 + 2 and 3n don't have any common factors, but their sum is n2 + 3n + 2 = (n + 1) (n + 2), which factors just fine. on Jan 22nd, 2014, 10:59am, rloginunix wrote:I take it that n, m and a are whole numbers, m is even. |
| I think we can further assume m>0 and a>0.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: factorable if m is odd
« Reply #8 on: Jan 23rd, 2014, 10:05am » |
Quote Modify
|
Yeah, I know. It "was" my plan. Wrong turn.
|
|
IP Logged |
|
|
|
|