wu :: forums - Print Page


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

        riddles >> easy >> Quadratic divisibility
        
(Message started by: NickH on Jun 13^th, 2003, 12:08pm)

Title: Quadratic divisibility
Post by NickH on Jun 13^th, 2003, 12:08pm

Show that, if n is an integer, n² + 11n + 2 is not divisible by 12769.

Title: Re: Quadratic divisibility
Post by THUDandBLUNDER on Jun 13^th, 2003, 4:31pm

:[hide]Not very elegant, I know:

Assume n² + 11n + 2 = 12769k = 113²k for some positive integer k

Solving for n, we get D² = (113)[1 + 4*(113k)²]

The first term (113) is prime
and the 2nd term is one more than a pefect square.

Therefore D² cannot be a perfect square.
Hence, n cannot be an integer.
[/hide]:

Title: Re: Quadratic divisibility
Post by Sir Col on Jun 14^th, 2003, 5:28am

T&B, I found the disciminant to be 113+4*113²k?

Knowing NickH's problems, there's going to be some ingenious lateral step required. Here are my rambings so far...

By defining f(n)=n²+11n+2, it is clear that f(n) will always be even and it is possible to show that f(n)==+/-1 mod 3; that is, f(n) is a and not a multiple of 3.

Transferring this to the RHS, 12769k, we determine that k must be of the form 6a+2 or 6a-2 if a solution exists.

However, I've not been able to take this any further. Anybody got any other ideas?

Title: Re: Quadratic divisibility
Post by THUDandBLUNDER on Jun 14^th, 2003, 9:30am

Quote:

T&B, I found the disciminant to be 17+4*113²k?

Duh. Yes, trying again I get 113*(1 + 4*113) = (113)(3)(151)
As these 3 numbers are all prime, D² cannot be a perfect square.

But, as you say, this is surely not the expected method.

Title: Re: Quadratic divisibility
Post by Sir Col on Jun 14^th, 2003, 10:40am

I just realised that I made a typo in my discriminant: I wrote 17 rather than 113?! ???

I think you forgot k this time T&B.

However, as the discriminant is 113(1+4*113k), we can see that the second factor is one more than a multiple of 113; that is, we can write it as 113(113t+1). Clearly this cannot be square, as the second factor cannot contain a factor of 113.

Title: Re: Quadratic divisibility
Post by THUDandBLUNDER on Jun 14^th, 2003, 11:41am

Quote:

I think you forgot k this time T&B.

Man, we are making hard work of this. :-[

Quote:

Clearly this cannot be square, as the second factor cannot contain a factor of 113.

I guess you mean '113 as a factor'.

Title: Re: Quadratic divisibility
Post by NickH on Jun 22^nd, 2003, 8:43am

Consider n² + 11n + 2 = (n + 62)² - 113(n + 34).

If n² + 11n + 2 is divisible by 113², it must be divisible by 113, and so (n + 62) must be divisible by 113. But then (n + 62)² is divisible by 113² while 113(n + 34) is not!