Associated Topics || Dr. Math Home || Search Dr. Math

### 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

- Doctor Schwa, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
Middle School Factoring Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search