Prime Factors of 4,194,305

Date: 09/20/1999 at 17:02:38
From: Carolyn Offutt
Subject: Prime Factoring 2^22+1

Dr. Math,

I am in 8th grade and taking Algeom (algebra and geometry in one 
year).  Our teacher assigned the problem:

     Prime Factor 2^22+1

I have spent about 2 hours on the problem so far, and have talked to 2 
of my classmates about it. I have been unable to make any progress 
other than finding out that one of the factors is 5. I worked out the 
number, which is 4194305, which is obviously divisible by 5.  I then 
found a program on the Internet that gives the prime factorization of 
a number. I entered my number and got 5*397*2113. We are supposed to 
show how we got our answer. I would like to know if you have a clever 
way to do this problem. I would appreciate it greatly.

Thanks!
Carolyn Offutt

Date: 09/20/1999 at 18:44:00
From: Doctor Schwa
Subject: Re: Prime Factoring 2^22+1

Interesting question, and I like your approach.

I tried to do it with a little algebra. Maybe you've learned by now 
that (x+1)^2 = x^2 + 2x + 1. Well, 2^22 + 1 looks sort of like that, 
except there's no 2x there. Rats. I thought for a while about how to 
put a 2x in there, and finally decided on this wishful thinking 
strategy:

2^22 = (2^11)^2, so if x = 2^11, then I have x^2 + 1. How do I get the 
2x? I just stuck it in there. But wait, that's not fair, so I better 
subtract it, too, like this:

     2^22 + 1 = 2^22 + 2*2^11 + 1 - 2*2^11.

Now I have that perfect square factoring pattern, but with a -2*2^11 
left outside:

              = (2^11 + 1)^2 - 2*2^11.

And 2*2^11 = 2^12, so

              = (2^11 + 1)^2 - 2^12

But 2^12 = (2^6)^2, so

              = (2^11 + 1)^2 - (2^6)^2

and now I use the 'Difference Of Two Squares' factoring pattern:

              = (2^11 + 1 + 2^6)(2^11 + 1 - 2^6)

which equals

              = (2113)(1985)

or (2113)(397)(5), the same answer you got.

Thanks for a fun problem. I wonder if my method is what your teacher 
had in mind?

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/