Determine whether or not N is a composite number, where
N = 675*2621 + 677*2610 - 1
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)
N is a composite number.
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!