Math 4281
Spring Semester 2006
Hints for exercise 4 of Sec 4A

 

As it says on the HW page, it's recommended to use a computer somehow. Indeed, it would be pretty tedious to do this problem completely by hand. On the other hand, it's not sufficient to just ask Mathematica or a similar program whether or not 44497 is prime.

Anyway, trial division is only method available to us at this time. Since the square root of 44497 is between 210 and 211, we can apply the result of E3 to conclude that it's enough to check factors between 2 and 210. While this helps somewhat, even this could be tedious.

You can use something as simple as Excel, or a similar spreadsheet, and most of my comments will be about that, but if you know how to program it in BASIC or any other computer language, that's fine too. In any case, it would be enough to check divisibility by primes between 2 and 199 (the largest prime below 210), but this would require us to have (or create) a list of primes. So, it's easier to just have the computer check disibility by the consecutive integers 2, 3, 4, ..., 210.

Here's a very basic version of a possible spreadsheet:
 

Desired values             Spreadsheet formulas
<>AB
1n44497/n
2222248.5
3314832.33
4411124.25
5......
            
<>AB
1n44497/n {labels only here, not formulas}
22=44497/A2
3=A2+1=44497/A3
4=A3+1=44497/A4
5...... {Use Fill Down to continue}

With this, we can inspect the resulting 209 (= 210-1) lines of output. If an integer appears as a quotient, we have a factor. Otherwise . . .

If we don't want to do something as tedious as inspecting the output, then our spreadsheet can be jazzed up somewhat. To do this, recall that the quotient in the division  44479 =nq + r  is the integer part of the fraction  44497/n. As it happens, most spreadsheet programs have a built-in function for integer part, namely  INT( ).  This appears in column C.  And finally, we get the remainder (in column D)  r  as  44497 - nq.  Thus:

Desired values             Spreadsheet formulas
<>AB CD
1n44497/n qr
2222248.5 222481
3314832.33 148321
4411124.25 111241
558889.4 88892
6......
            
<>AB CD
1n44497/n qr {labels only, not formulas}
22=44497/A2 =INT(B2)=44497-A2*C2
3=A2+1=44497/A3 =INT(B3)=44497-A3*C3
4=A3+1=44497/A4 =INT(B4)=44497-A4*C4
5=A4+1=44497/A5 =INT(B5)=44497-A5*C5
6...... ......{Use Fill Down to continue}

So far so good, but does this story have a punch line? Well, if there is an integer factor, then 0 will have to occur as a remainder. We can look at our output to try to see it, but this still leaves a human in the loop. Now, since the remainders are non-negative integers, what about asking the spreadsheet to do this?? Well, the spreadsheet function for finding the smallest value in a row, column, or array is MIN( ).
 

Back to  the class homepage.

Back to  to the homework page.