Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Several Problems
Replies: 5   Last Post: Nov 24, 1996 3:52 PM

 Messages: [ Previous | Next ]
 Scott Phung Posts: 32 Registered: 12/6/04
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.

Date Subject Author
11/21/96 Scott Phung
11/22/96 me
11/22/96 me
11/23/96 Scott Phung
11/22/96 Bob Silverman
11/24/96 JuanVP