All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 A Composite Determination Problem (Posted on 2006-04-23)
Determine whether or not N is a composite number, where

N = 675*2621 + 677*2610 - 1

NOTE:
A prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. A composite number is a positive integer which has a positive divisor other than one or itself. By definition, every integer greater than one is either a prime number or a composite number. The numbers 0 and 1 are considered to be neither prime nor composite.

 Submitted by K Sengupta Rating: 4.3333 (3 votes) Solution: (Hide) N is a composite number. EXPLANATION: N = 675*(26^21) + 677*(26^10) - 1 = 26^23 - 26^21 + 26^12 + 26^10 - 1 = x^23 - x^21 + x^12 + x^10 -1; where x =26 = x*(x^20)*(x^2 -1) + (x^10)*(x^2 +1) = (a^2)*x*(x^2 - 1) + a(x^2 + 1) -1; where a = x^10 = (a^2)*x*(x^2 -1) + a(x^2 + x) - a(x-1) -1 = ax(x+1)(a(x-1) +1) - a(x - 1) -1 = (a(x-1)+1) (ax(x+1) - 1) = ( 25*(26^10) + 1) ( 702*(26^10) - 1) = A*B, where: A = 25*(26^10) + 1, and B = 702*(26^10) - 1 Now, A = 25*(26^10) +1 > 1. Also, N > 675*(26^21) + 677*(26^10)> 1 + 25*(26^10) = A Accordingly, 1< A< N Since, B = N/A, it follows that: 1< B< N Hence, N is a positive integer which posesses at least two positive divisors other than one or itself. This is in conformity with the definition of a composite number given in the problem. Consequently, N is a composite number. ------------- Q E D ----------- ALTERNATE SOLUTION:(Submitted By Frederico Kereki) I supposed there had to be some factoring of x^23-x^21+x^12+x^10-1. I decided to go the easy way, and look for two factors like a.x^p+b.x^q+1 and c.x^r+d.x^s-1. (At least, the -1 would be produced.) Multiplying suggests that c=1/1 and r=23-p, so now we are looking at a.x^p+b.x^q+1 and (1/a).x^(23-p)+b.x^s-1. Doing the multiplication produces SIX terms, that reduce to five if 23-p+q=p. In order to get the other exponents to match, p+s=21 and q+s=10, which finally produces p=12, q=1, and s=9. Equating terms, finally gets to a=-b=-2 and c=-d=-1/2. So, the original polynomial is the same as (-2.x^12+2x+1) multiplied by (-1/2)x^11+(1/2).x^9-1, and for x=26, both terms are integer and way greater than 1, so N is composite!

Comments: ( You must be logged in to post comments.)
 Subject Author Date re: Another Stab at the Solution Ady TZIDON 2006-05-03 01:06:31 No Subject xdog 2006-04-28 09:42:30 re(2): A first stab at the solution xdog 2006-04-27 16:17:13 re: A first stab at the solution Federico Kereki 2006-04-23 19:10:55 Solution Nick Hobson 2006-04-23 18:29:27 brute force Charlie 2006-04-23 14:40:04 does this make sense? Jer 2006-04-23 13:43:24 Solution Tristan 2006-04-23 13:25:07 re: A first stab at the solution Jer 2006-04-23 13:21:48 A first stab at the solution e.g. 2006-04-23 12:10:50 re: Another Stab at the Solution (Whoops again) tomarken 2006-04-23 11:10:02 Another Stab at the Solution tomarken 2006-04-23 11:05:47 re: Solution (Whoops) tomarken 2006-04-23 10:57:43 Solution tomarken 2006-04-23 10:54:04
Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

 Search: Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information