I was told that the number 1,000,001, no matter what base you're working in, is a composite number. Is this true?

Hmm...that's an interesting question. Let's look at some sample bases to make sure it's a reasonable statement.

If this was base ten, then we'd have 1,000,001 is divisible by 101, so it's composite.

If this was base eleven, then the number would be equal to 1,771,562 (base ten), which is obviously composite, because it's even!

Actually, now that I think about it, any time the base is an odd number, 1,000,001 represents an even number, so it's definitely true for all odd bases. So let's focus on even numbered bases.

Let's try base eight. This number would be equal to 262,145 (base ten), which is a multiple of 5.

Base six? That's 46,657 (base ten), which is divisible by 37.

Now, I could keep trying more bases, but I just noticed something interesting. In our first example, the number is divisible by 101, which is one more than the square of 10, and in our last example, 46,657 is divisible by one more than the square of six. That's interesting. Your number may always be divisible by one more than the square of the base. Let's test that hypothesis.

In base twelve, this number would be 2,985,985, and if our hypothesis is correct, it will be divisible by 12² + 1, or 145. Pull out your calculator...

It is!

So we have a reasonable extension of your conjecture: If 1,000,001 is a number written in base n, then it is divisible by n² + 1.

Ideally, it would be nice if we could prove this extension, because if we could, we'd be closer to proving your conjecture.

Let's write our number 1,000,0001 in terms of the base n:

1,000,0001 = 1·n⁶ + 1.

And suddenly I'm remembering one of my factoring rules - the rule for a sum of cubes:

n⁶ + 1 = (n²)³ + 1³ = (n² + 1)(n⁴ - n² + 1)

Sure enough, 1,000,0001 will always be divisible by one n² + 1!

So in order to finish proving your conjecture, we simply need to show that (n² + 1) can't be equal to 1, and it can't be equal to n. These are the two circumstances which could result in  n⁶ + 1 being prime (a number is composite if it has factor pairs other than one and itself).

n² + 1 = 1 has only one solution: n = 0. But we don't work in base zero, so this is irrelevant.

n² + 1 = n, or n² - n + 1 = 0, which has no real solutions, so YES! The conjecture we started with is true!

Thanks for asking - that was an interesting exercise!
Professor Puzzler