Find remainder when x^100 is divided by x^2 - 3x + 2

[LCKurtz]

begin {offtopic}

Sambarbarian, I am curious to know if you grew up in or near northeastern South Dakota. If your answer is yes, I will tell you why I thought that. Otherwise nevermind.

end{offtopic}

nopes , I am an indian ... but please tell me y u thought that

Because I did grow up in South Dakota, and I have met people from the eastern part of the state that use the word "dint" when they mean "didn't", which is a contraction for "did not". The word "dint" means something else.

 

[eumyang]

You'll notice that 2⁹⁹⁹ is not a factor of 10⁹⁹⁸. In fact, any factor of 10⁹⁹⁹ that is divisible by 2⁹⁹⁹ cannot be a factor of 10⁹⁹⁸. So how many of these factors of 10⁹⁹⁹ would that make altogether? (And no, the answer to this question is not the final answer of the problem.)

No, I believe Eumyang was thinking about numbers like $2^{999} \cdot 5$, $2^{999} \cdot 5^4$ and $2^{999} \cdot 5^{999}$ (just examples). Have you considered those?

There are many more such numbers to consider.

Right. 2⁹⁹⁹ (or 2⁹⁹⁹ x 5⁰) is not a factor of 10⁹⁹⁸.
2⁹⁹⁹ x 5 (or 2⁹⁹⁹ x 5¹) is not a factor of 10⁹⁹⁸.
2⁹⁹⁹ x 5² is not a factor of 10⁹⁹⁸.
These are some of the factors of 10⁹⁹⁹, divisible by 2⁹⁹⁹, but are not factors of 10⁹⁹⁸. So how many factors would this make altogether?

 

[Curious3141]

nopes , I am an indian ... but please tell me y u thought that

Well, hello, I'm (ethnically) Indian too, although I'm a Singaporean by birth and citizenship.

And as LCKurtz points out, "dint" has its own meaning. It means by virtue of (something) when used in a phrase like "by dint of his dogged hard work". It's usually used emphatically, to suggest force, power or perseverance. It can also be an alternative spelling for "dent".

Back to the math now!

 

[sambarbarian]

right. 2⁹⁹⁹ (or 2⁹⁹⁹ x 5⁰) is not a factor of 10⁹⁹⁸.
2⁹⁹⁹ x 5 (or 2⁹⁹⁹ x 5¹) is not a factor of 10⁹⁹⁸.
2⁹⁹⁹ x 5² is not a factor of 10⁹⁹⁸.
These are some of the factors of 10⁹⁹⁹, divisible by 2⁹⁹⁹, but are not factors of 10⁹⁹⁸. So how many factors would this make altogether?

999 + 999 = 1998 ?

 

[Curious3141]

999 + 999 = 1998 ?

I have one more than that. How did you arrive at your figure (exactly)?

 

[HallsofIvy]

Now you are just guessing. The critical point is that $10^{998}= (5^{998})(2^{998})$. That means that $5^n$ is a factor for every n from 0 to 998. But it also means that $2^n$, for n= 0 to 99 is also a factor. That's 2(999) right there, and and we haven't even started combining "2"s and "5"s.

One way to look at it is this: there are 999 ways to find factors using only "5"s and there are 999 ways using only "2"s. And the "fundamental theorem of counting" says that the if there are m ways of doing one thing and n ways of doing another (independently of the first) then there are mn ways of doing both.

 

[Curious3141]

Now you are just guessing. The critical point is that $10^{998}= (5^{998})(2^{998})$. That means that $5^n$ is a factor for every n from 0 to 998. But it also means that $2^n$, for n= 0 to 99 is also a factor. That's 2(999) right there, and and we haven't even started combining "2"s and "5"s.

Yes, but everything from $5^0$ to $5^{998}$ are also factors of $10^{998}$ and are therefore excluded from consideration. Ditto for powers of 2. Every number that should be considered should have as a factor, either $2^{999}$ or $5^{999}$ or both (the only one that has both is $10^{999}$).

 

[sambarbarian]

i don't quite understand

 

[Curious3141]

i don't quite understand

OK, start by considering the numbers with $2^{999}$ as a factor. Now, everything from $2^{999}.5^0$ to $2^{999}.5^{998}$ divides $10^{999}$ but not $10^{998}$. Agreed? So how many is that?

Now consider numbers with $5^{999}$ as a factor in a similar way. How many do we have here?

Finally, don't forget $2^{999}.5^{999} = 10^{999}$ itself, which I avoided including till the last step so that we don't double-count it.

 

[sambarbarian]

OK, start by considering the numbers with $2^{999}$ as a factor. Now, everything from $2^{999}.5^0$ to $2^{999}.5^{998}$ divides $10^{999}$ but not $10^{998}$. Agreed? So how many is that?

2^999 . 5^0 is equal to 2^999 . 5^1 ,,, (998 - 1) = 997 ? i am not sure

 

[Curious3141]

2^999 . 5^0 is equal to 2^999 . 5^1 ,,, (998 - 1) = 997 ? i am not sure

You're not thinking clearly, and what you wrote makes no sense.

$2^{999}.5^0 = 2^{999}$ because any nonzero number raised to the power zero is 1.

$2^{999}$ is still a number you have to include in the count because it divides $10^{999}$ but not $10^{998}$.

I asked you to count the numbers from $2^{999}.5^0$ to $2^{999}.5^{998}$ going in consecutive exponents of 5. This is equivalent to counting the integers from 0 to 998 inclusive. You replied with '997'. Sure of this?

How many integers are there from 0 to 1 inclusive? 0 to 10? 0 to 998?