Quote:
|
Originally Posted by esjay
nagi yeh euler no ka funda kya hai. iknow fermat's thrm. is there ne link where it is explained
|
Originally Posted by
khanna_sumit
This one is for ignorant buddies who find remainder problems and theorems related to it hard to understand.
I believe that algebraic number theory is one of the most intriguing topics of mathematics. Numbers have enchanted mathematicians for centuries and still there is much to be explored. Here is a set of theorems that can be used to solve almost all the problems related with finding remainders. Before starting lets prove that number of primes are infinite. Suppose I have found first few primes as p(1) = 2; p(2) = 3 and so on up to p(n). Product p(1)*p(2)*…*p(n) is divisible by all the primes we have found so far.
That means p(1)*p(2)*…*p(n) + 1 is not divisible by any of the known primes. That means either this number is a prime or it is a composite number having prime factors different from that are known (Caveat: -We have no right to say that this number is prime unless we prove it. A number of coaching institutes say this number is a prime but this is not necessarily true). Hence if we have first n primes we can find at least one more prime and that proves infinitude of primes. Wasn’t it a simple way of proving something of quite an elusive nature? Well that’s the beauty of mathematics.
Why does ISO insist upon standardizing the methods and approaches of running a business? Because when you follow same process again and again, you become proficient at using the process that brings the efficiency and quality in products and services. So if we follow a prescribed set of rules, we will become proficient at solving even difficult remainder problems.
It is necessary to know how a remainder is formally defined. Suppose we have two positive numbers a, b where a>b. a = b*q + R is true for infinite sets of integers (q, R).
Lets say that R is the residue (because we have not defined remainder as yet). We define remainder as value of R that is numerically less than the divisor b and either negative or positive. Or ˝r˝ < b. A sample statement “ When a number is divided by 29 leaves a remainder 5.” should be interpreted as N = 29x + 5. I won’t explain the trivial cases that are given in almost all the materials, as when a number is divided by two different divisors, remainders are same then remainder when LCM divides the number gives the same remainder etc. Here are the theorems you must know.
First thing we should be clear about is that whatever operation (addition, subtraction or multiplication) happens on the numbers, same operation happens on the remainders of the numbers from a given divisor. Suppose 2 numbers x and y when divided by divisor ‘a’ leave remainders r and R i.e. x = am + r and y = an + R.
(x + y) = a(m + n) + (r + R) hence remainder when (x + y) is divided by a is either (r + R) or remainder when (r + R) is divided by a ( in case r + R is greater than a).
Similarly (x – y)%a = (r – R)%a and also (x*y)%a = (r*R)%a. (read % as remainder from divisor).
I presume everyone knows the application of binomial theorem in finding remainders so won’t explain here.
RULE 1. Chinese remainder theorem: - Do not panic by looking at the name. It is just another buddy that helps in solving remainder problems. I will explain it using a sample problem.
Q. A number when divided by 7 leaves remainder 5 and when divided by 11 leaves remainder 3, find a general solution. There may be easier methods available for solving these questions but motive here is to understand the approach that more or less remains the same even when we move towards questions of higher level. From given statement we can say that number N = 7x + 5 = 11y + 3.
Or x = (11y – 2)/7
Lets say that y when divided by 7 leaves a remainder r i.e. y = 7a + r. 11 leaves either 4 or –3 as remainder from 7 (at times negative remainder makes the calculations easier). Since x is an integer, it gives remainder 0 when divided by 7 therefore 4r – 2 is divisible by 7 since r is the remainder from 7, you’ll have to try values of r up to 6. At r = 4, 4r – 2 becomes divisible by 7. So we can say here that y = 7a + 4. Putting the value of y in N=11y + 3 = 11(7a + 4) + 3 = 77a + 47. Putting a = 0, 47 is the first number of this type and 77a + 47 is the general series of such numbers.
I hope you can understand the process. Now lets say that in the same question another condition is given that when divided by 13, number leaves a remainder 6.
That means N = 13b + 6 along with the previous conditions. We have already solve it for two conditions and found the combined form as 77a + 47. We just need to solve this with the new form 13b + 6.
77a + 47 = 13b + 6
Or b = (77a + 41)/13.
Again using the same process.
77%13 = -1 (Usefulness of negative remainders)
41%13 = 2 (Positives are equally useful)
That clearly means that a%13 = 2
(-1)*(2) + (2) = 0{I have done the same operation on remainders as done on numbs}
Therefore a = 13c + 2; and putting this value in 77a + 47 = 77(13c + 2) + 47
= 1001c + 154 + 47 = 1001c + 201.
Whatever other remainder conditions are given, we can solve in same fashion.
Now you know CHINESE REMAINDER THEOREM.
You need practice to master it. Do you require questions on this? I don’t think so. You can make as many as you wish to.
RULE 2: FERMAT’S LITTLE THEOREM
Using the properties of infinite arithmetic progressions, Fermat proved the theorem that for a prime number ‘p’ that is co prime with another number ‘a’; when a to the power
(p-1) is divided by p, remainder is 1. Or a^(p-1) % = 1. Don’t forget that this theorem is defined only for prime divisors. E.g. 2^4%5 =1; 3^10%11 = 1. Or in more general form
a^{n(p-1)}%p = 1. So if the question is 2^1000%11, remainder will be 1 because power of 2 is a multiple of (11-1).
What if divisor is not a prime? Then we have eular’s generalization of Fermat’s rule.
That generalization says that a^e(n)%n = 1. Where e(n) is eular’s number for divisor n. Also a is co prime with the divisor p. Eular’s number e(n) for divisor n is defined as number of natural numbers less than ‘n’ and co prime with it. How to find e(n)? Suppose I want to find eular’s number of 1001. Prime factors of 1001 are 7,11,13.
e(1001) = 1001(1-1/7)(1-1/11)(1-1/13). In general for a number n having prime factors p1, p2, p3…. e(n) = n (1-1/p1)(1-1/p2)(1-1/p3)…
This knowledge about eular’s theorem is sufficient. Now that we know fermat’s rule and eular’s rule, lets try a sample question.
What are last two digits of 3^96? Last two digits of this number can be obtained by finding remainder when this number is divided by 100. 100 = (2^2)*(5^2). Understand the things clearly here. For 2^2 i.e. 4, eular’s number is 4(1-1/2) = 2 and for 5^2 (25), eular’s number is 25(1-1/5) = 20. Using eular’s theorem, 3^2 %2^2 = 1 and
3^20 %5^2 = 1. if we take LCM of the powers of 3 in two cases(LCM is 20) we find that 3^20 %100 = 1 or last two digits of 3^20 are 01. It can be proved for any other number co prime with hundred. That explains why cyclicity of last two places is generally 20 for all numbers co prime with 100. Last 2 places of 3^96 will therefore be same as last two places of 3^16. (Because 3^96 = 3^80 * 3^16 and 3^80 ends in 01) . How to find last two digits of 3^16? 3^20 = 3^16 * 3^4 lets say last two digits of 3^16 are xy.
Therefore xy * 81 = 01 (considering only last two digits) that’s true for xy = 21.
Another question. What is the remainder when 3^1001 is divided by 1001?
1001 = 7*11*13. 3^6 %7 = 1; 3^10 %11 = 1 and 3^12 %13 = 1. That implies
3^{LCM (6,10,12)} %1001 = 1 or 3^60 %1001 = 1. Using this we can reduce the previous problem into a simpler one. 3^1000 = 3^960 * 3^41, from 3^960, remainder is 1 therefore reminder when 3^1001 is divided by 1001 is same as remainder when 3^41 is divided by 1001. 3^41 %7 = 3^5 %7 = 5 {I presume it should be clear by now}
3^41 %11 = 3
3^40 %13 = 3^5 %13 = 9. It is a number which when divided by 7,11 and 13 gives remainders 5,3 and 11 respectively. N = 7x + 5 = 11y + 3 = 13z + 9. Further we know how to solve it (HINDI CHEENI BHAI BHAI).
I am attaching a list of questions few of which are collected from various threads and a few are made by me. Lets solve all those using the standard methods we have learnt. Solving the problems will make concepts clearer. Remember; try to standardize your approach.
Regards
Sumit.
1.What is the remainder when 17^19 + 13^19 is divided by 25?
2.Find the remainder when 104^303 is divided by 101.
3.Find the last two digits in the expansion of 2^ 999.
4.Find the remainder when 2 ^ 1990 is divided by 1990.
5.Remainder when (128 )^500 is divided by 153.
6.Find last 3 digits of 3^1994.
7.What is the remainder when 2^2001 is divided by 2001?
8.What is the remainder when 2^2002 is divided by 2002?
9.What is the remainder when 13^2404 is divided by 2310?
10.What is the remainder when 2^10013 is divided by 3125?
11. Find last 4 digits of (2319)^{10^12 + 2}.
And a lengthy one here.
12. What is the remainder when 17^28820 is divided by 30030?
Solve these first and I’ll post more related with the topic.
well i can add the concept of inverses.. of numbers..
considier
8^828/167 ...
we know 8^830/167 gives one as remainder.
and for 167.. 21*8 =168 so 21 is the inverse of 8.. then 21^2/167 .. gives 107..
similiarly u can try 31^78/123 .. will give 16..and so on.. u can also use chinese remainder theorem to solve it.
further additions
Originally Posted by tatimatla
hmm...here it goes...
generally what we understand from Euler's theorem is:
x^euler(y) % y = 1 , if x and y are mutually prime.
now euler's sometimes a huge number...and we have many problems where the power of 'x' is on the negative side of the euler...say euler(y)-1, euler(y) -2 and so on...
for this we find the inverse equivalent of x -> z.
z is the least natural number such that x*z mod y = 1
when such z is found,
we can safely conclude that
x^(euler(y) - k) mod y = z^k mod y.
that's the basic funda...
SPRITE?
my take 17^19mod 25 =
17^-1mod 25 =3..
okay the conceptof inverses goes as this..
consider
a^p/n .. where aand p are coprime.. well do they need to be..(think on that...)
now we used euler number concept to destroy the power..
or we use fermat little theorem.. then we can use remainder theorem and all.. right..
or use chinese remainder theorem..
instead of that.. we can use inverse..
think .. of 2001 ..
last three digits are 001 ..
so its gives remainder as 1.. when divide by 1000
so... its gives the inverse of 3..
667 ..667 =23*29.. so we can't can any inverse of.. this number..
this concept can used to find the last digts easily..
1)31^78/123..find the remainder
now the inverse of 31 is .. 4.. for 123..
31*4 =123+1 .. so..
31^-2 can be written as 4^2 .. and gives 16..
consider other questions.. think in terms of inverses.. its requires tables.. and thinking in terms of factors always..
like from the chocies u will be able to figure out the inverses.. easily..
its pretty similiar to CRM.. crm is a process.. inverses are intuitive..
nagi's take
so for
31^78/123
EU for 123 = 80
means 31^-2 = 4^2 = 16
so if a. i mod p =1 then we can take a=1/i any where
Help
Linear Mode
