Home > Numbers
| 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?
|
|
Submitted by K Sengupta
|
|
Rating: 3.7500 (4 votes)
|
|
|
Solution:
|
(Hide)
|
7*x^25 = 10 (Mod 83)
or, 7*x^25 = 259 (Mod 83)
or, x^25 = 37( Mod 83)
Now, x^83 = x( Mod 83); since 83 is prime.
So, x^575
=(x^83)^6 * x^77 (Mod 83)
= x^6 * x^77 (Mod 83)
= x^83(Mod 83)
= x (Mod 83)
But, x^575 = (x^25)^23 = 37^23( Mod 83)
Now, 37^2 = 41(Mod 83); 37^3 = 23 (Mod 83)
37^5 = 41*23 (Mod 83) = 30 (Mod 83)
or, 37^10 = 70 (Mod 83)
or, 37^20 = 3(Mod 83)
or, 37^23 = 3*23 = 69(Mod 83)
Hence, the required minimum value of x is 69
|
Comments: (
You must be logged in to post comments.)
|
|
Please log in:
Forums (1)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
