Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Several Problems
Posted:
Nov 21, 1996 9:17 PM


Hello Folks, i have several problems i wish to clear up:
The Problems deal with Congruences, Prime Factorization, and Roots of Polynomials. (It's not very advanced stuff / questions, I'm just in high school).
Congruences 1) Say i have a large number expressed in exponential form (ie. 13^887). Using congrueces i am able to detect the last 1, 2, 3, etc. digit by using mod 10, 100, 100, etc. respectively. The main part i am concerned about is speed and efficiency.
On a previous math contest, I was to find the 'fourth' digit from the right of 11^86. After using the majority of the time allowed for this contest, i found it to be 6. I was correct though, but it suckered the time remaining i had for the other questions.
I used the successive powers of 2 method. (ie 2, 4, 8,.., 64). I then found the congruent parts to 11^2, 11^4, 11^8,.., 11^64 by sucessive squaring. I then multipled their congruecent parts to obtain the answer. But is this the most efficient method? Or is it the General method?
The answers used this method. Starting with 11^5, they squared it and got a congruent part to 11^10. They then went on to 11^20, 11^40, 11^80. They they multipled the 11^80 congruent part by 11^5's congruent part and 11's congruent part. This then gives the answer.
What i am looking for is that given an exponent for any number, what is the most effective and fastest way to find it's congruent modulo m. I think so far, you should use pure wit and guesses. Is there a systematically / fast / efficient way to do this?
Take 86 for example. I used the sequence 2, 4, 8, 16, 32, and 64. Thus 86 = 64+16+4+2. I have used 6 successive squares. They answer was given from the sequence 5, 10, 20, 40, 80. Thus 86 = 80+5+1. They have used 5 sucessive squares.
Try this with the exponents 327 and 93.
Remark. It is easy to find a number's moduluo 10,000 in this case. You just take the last four digits, since subtracting 10,000 successivley does not alter the last four digits. I didn't use / know this during the contest :(
Prime Factorization 2) This probably has been asked before, but what is generally the way to go when trying to factor large numbers. By large numbers, i mean numbers that are factorable with a simple calculator and a method, thus no programming stuff. I have learned so far of three (inefficient) ways.
* Seive of Eratosthenes (Try using this on a contest!) * If p is prime, p has no factors less than the square root of p. (Ok, but for the smaller numbers < 1000) * Fermat's difference of squares method, where you add the square of an integer bigger than the square root of p, and then see if it's a perfect square. ie. For 102, try 102+11^2, then try 102+12^2, etc until you find a perfect square. Then you can use algebraic methods to find the factors or p.
Again, i'm looking for good, fast ways to factor p, probably for numbers smaller than 100,000. Also, any ways to tell if p is prime or not would be nice (without factoring first).
Polynomials 3) Finding the roots of polynomials has gotta be the number two pain killer for mathematics for a long time (FLT was # one, but I believe it has been already solved by Wiles). I'm just concerned over what techniques to use.
First i shall list MY known techniques/tools. 1) Synthetic Division (Very essential) 2) Rational Root Theorem 3) Descartes Rule of Signs (Very essential) 4) Upper and Lower Bounds of Roots 5) I have two "No rational root theorems". 6) Fundamental Theorem of Algebra.
These are also good things to know, but i really don't perfer them, since the answers aern't exact. 1) Bisection method 2) Newton's method. 3) Graphing with Calculus methods.
Suppose then i have a polynomial f(x) with degree n, first term doesn't equal zero, and a nonzero constant (last term doesn't equal zero), assuming f(x) cannot be easily factored.
  How do i go about solving it?  
I use the no rational root theorems and see if there are no rational roots. Hopefully there will be at least one rational root.
Then i use Descarte's Rule of Signs to note the positive and negative and remaining nonreal zeros, constructing a chart.
I then use the Rational Root theorem to list the possible choices. (I will eliminate all the positive or negative choices if Descartes Rule of Signs shows there are no possible positive or negative real solutions, respectively).
I start at the middle of the pile for the positives, to see if it is an upper bound. Then I start at the middle of the negative choices and see if it is an lower bound. I jump around randomly and see what I can do. (I'm using synthetic divison, by the way).
I will find a root then factor it into a divisor and quotient type. I will then revise the list of rational roots and update if possible Descarte's rule of signs chart.
I will complete this process on the lower degree polynomial i have.
In the case of no rational solutions, i will graph the polynomial and use the bisection method two or three times. Then i will use newtons method to find the real solutions. I don't know however what i can do about the nonreal solutions.
But is there something i am missing here? Important Theorems? A missing step? A faster, better way to do this factoring? Take a guess at the imaginary solutions?
Thanks, Scott.



