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

Home > Just Math
A Composite Determination Problem (Posted on 2006-04-23) Difficulty: 3 of 5
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 SolutionAdy TZIDON2006-05-03 01:06:31
No Subjectxdog2006-04-28 09:42:30
re(2): A first stab at the solutionxdog2006-04-27 16:17:13
Solutionre: A first stab at the solutionFederico Kereki2006-04-23 19:10:55
SolutionSolutionNick Hobson2006-04-23 18:29:27
Solutionbrute forceCharlie2006-04-23 14:40:04
Some Thoughtsdoes this make sense?Jer2006-04-23 13:43:24
SolutionSolutionTristan2006-04-23 13:25:07
re: A first stab at the solutionJer2006-04-23 13:21:48
Some ThoughtsA first stab at the solutione.g.2006-04-23 12:10:50
re: Another Stab at the Solution (Whoops again)tomarken2006-04-23 11:10:02
SolutionAnother Stab at the Solutiontomarken2006-04-23 11:05:47
re: Solution (Whoops)tomarken2006-04-23 10:57:43
SolutionSolutiontomarken2006-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 (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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