All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 A Smallest Integer Problem (Posted on 2006-12-13)
Find the smallest positive integer x for which (7x25 - 10)/83 is an integer.

Can you do this in a short time using pen and paper, and eventually a hand calculator, but no computer programs?

 See The Solution Submitted by K Sengupta Rating: 3.7500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 thoughts | Comment 1 of 2

7 x^25 is to be 10 mod 83.

Fortunately 12 * 7 = 84, which is 1 mod 83. So we need x^25 to be congruent to 12 * 10 = 120 mod 83; that is, congruent to 37.

Unfortunately I don't know a way of finding a number whose 25th power is congruent to 37 mod 83, except by trial and error, which I wouldn't want to do without a program. Perhaps a programmable calculator (TI-83 for example) program, or use of the table feature, would be acceptable.

The trick to avoid the need for extra precision is to raise any trial number to the 5th power, reduce it mod 83, and then raise that number to the 5th power and again reduce mod 83. If the result is 37, you've got x as the number you started with.

 Posted by Charlie on 2006-12-13 08:44:48

 Search: Search body:
Forums (0)