wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> factorable if m is odd
        
(Message started by: Christine on Jan 17^th, 2014, 4:20pm)

Title: factorable if m is odd
Post by Christine on Jan 17^th, 2014, 4:20pm

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

Title: Re: factorable if m is odd
Post by pex on Jan 18^th, 2014, 1:07am

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 n^m+2 - n^m to the polynomial, which factors as (n+1)(n-1)n^m, so divisibility by n+1 is preserved. It leads to

n^a + n^a-1 + n^m + 1 = (n + 1) (n^a-1 + n^m-1 - n^m-2 + ... - n + 1).

Title: Re: factorable if m is odd
Post by rloginunix on Jan 21^st, 2014, 1:26pm

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.

Title: Re: factorable if m is odd
Post by pex on Jan 21^st, 2014, 1:52pm

on 01/21/14 at 13:26:48, rloginunix wrote:

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.

Title: Re: factorable if m is odd
Post by rmsgrey on Jan 22^nd, 2014, 7:58am

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 n^a+n^a-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.

Title: Re: factorable if m is odd
Post by pex on Jan 22^nd, 2014, 10:35am

My understanding is that we're looking for p_a,m(n) = q_a,m(n) r_a,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.

Title: Re: factorable if m is odd
Post by rloginunix on Jan 22^nd, 2014, 10:59am

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.

Title: Re: factorable if m is odd
Post by pex on Jan 22^nd, 2014, 12:49pm

on 01/22/14 at 10:59:52, 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, n² + 2 and 3n don't have any common factors, but their sum is n² + 3n + 2 = (n + 1) (n + 2), which factors just fine.

on 01/22/14 at 10:59:52, 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.

Title: Re: factorable if m is odd
Post by rloginunix on Jan 23^rd, 2014, 10:05am

Yeah, I know. It "was" my plan. Wrong turn.