106can anyone explain me femat's theorem, i am giving INMO and need to know something about it....
Find the remainder when (1!+2!+3!+...+2007!)^500 is divided by 7...
#This question is directly copied from a standard buk... juzz wanna know different ways of solving it...
-
UP 0 DOWN 0 0 54
54 Answers
106
1if there is something wrong it is in the prev. part of the soln.
13well then... it can (almost) be concluded dat d answer is 4... thnx evry1... [1]
btw philip... can u please explain me whats dis method of mod... giv me a brief n precise explanation... thanq...
1sorry Maq cant help you more on the topic
maybe Nishant bhaiyya can help you more
prophet also knows one or two handy methods using congruences
i ,for now, read only a bit of modular and all of that i ve posted in my previous thread
62see basically we all agree that the remainder will be same as
(1+2+6+24+120+720)500
this will give the same remainder as
(873)500
(7k+5)500
this will give the same remainder as
5500
5 - > 5
52 - > 4
53 - > 20 -> 6
56 - > 53.53 - > 6.6 -> 36 ->1
so
56 gives a remainder 1 on division by 7
5^500 = 5^498. 25 -> (5^6)^83. 25 -> 1.25
this will give a remainder as 25 =4
62dont be afraid by the solution above... it is simple.. try to see carefully :)
13yeah bro... me too solved it similarly... but i want to know about d modular method suggested by philip... explain me the definition of modular method as briefly n precisely as u can... thanq... [1]
62oh ok.. din read properly..
See maq,
we say that
a≡b (mod c) read as a is congruent to b mod c
if c divides a-b
if a≡b (mod c)
then
an≡bn (mod c)
an≡bn (mod c)
1hey Maq its the same method after 5500 only b4 it was slightly different
if you can understand this then you got all i had said about
1all done and dusted ......
now this thread deserves to be highlighted [1]
341As already mentioned for all n>6, 7 divides n!. So you only have to consider (1!+2!+...+6!)500
their sum (sometimes denoted by !6) leaves a remainder of 5 or -2
So (1!+2!+...+6!)500 wil leave the same remainder as (-2)500 which is equal to 2500
Now from fermat's theorem 26 will leave a remainder of 1. Hence 2498 will also leave a remainder of 1. Hence 2500 will leave a remainder of 4
62bhai prophet.. ppl will get scared seeing fermat's theroem :D
:D
13i couldn't find anything wrong in ur method gagar... but d answer is not 4, it is 2...
dis question is referred from TMH→P&C→level 2→section1→prob no. 9 .....
juzz check it once if u have d buk wid u... plzzz...
62Fermat's Last theorem: (This one was one of the most challenging and well known in the history of mathematics... got solved only 4-5 yrs back!)
If an integer n is greater than 2, then the equation an+ bn = cn has no solutions in non-zero integers a, b, and c.
Fermat's little theorem : if p is a prime number, then for any integer a,
a^p ≡ a (mod p)
62Fermat's little theorem there is a easy proof .. but that needs group theory.. which you will not study till u do some pure mathematics... in the future....
I dont know of a simpler proof...
Fermat's last thoerem took a few centuries... i dont know the proof of it
It was solved only near the year 2000 AD... That too i think by the use of computers... !!
341No bhaiya, not by computers but by Andrew Wiles, but with very advanced techniques.
Those who know congruences can understand little theorem easily
If you consider a prime p, the numbers 0, 1,2,...,(p-1) are all distinct remainders on division by p
Let a be a number prime to p.
Consider a, 2a, 3a,..., (p-2)a, (p-1)a. There are p-1 numbers here
All of them leave different remainders on division by p, for is some two numbers am and an leave the same remainder then their difference a(m-n) would be divisible by p. But a is prime to p and |m-n|<p and hence cannor be divisible by p. Also, none of these numbers are divisible by p.
Hence these numbers are congruent to 1,2,...,(p-1) in some order
Hence a X 2a X 3a X...X a(p-1) ≡ 1 X 2 X 3 X...X (p-1) mod p
and hence ap-1 ≡ 1 mod p (We can divide by (p-1)! on both sides since it is prime to p)
Actually, this is a special case of the Euler-Totient theorem, which states that if m is a natural number, then consider the set of numbers less than m and prime to it. The cardinality of this set (i.e. the number of members of this set) is denoted by φ(m).
e.g. if m = 6, we have 1,5 are prime to 6. hence φ(6) = 2.
Then, if a is a number prime to m, we have aφ(m)≡1 mod m
If m = p where p is a prime, then obviously φ(p) = p-1 and Fermat's Little Theorem follows.
62prophet.. i was talking about fermat's last theroem :)
this proof you give is fermat's little theorem...
341proof of fermat's last theorem runs into 300 pages bhaiya. and i dont think that if i study math my entire life i will be able to understand it!
hope u dont order me to learn and write that proof :D
62lol.. yeah i know that it runs into a few hundred pages :D
anyways i may be wrong in stating the thing that he used computers.. (I think he did!) but as i said i may be wrong :)
1i just wanna clear my little doubt 'bout this little theo.
is it necessary
or necessary & sufficient both
bcoz i've heard of something by the name carmichael numbers
and yet this test is used to find probability of the no. being prime
btw talking about the last theo I have the proof in a pdf file which i never opened after downloading and yes prophet is rite about its length and complicatedness [4]
341actually carmichael numbers are called pseudoprimes because they too satsify this property for numbers that are prime to them. The smallest such number is 561.
Hence this is not a sufficient condition.
There is a concept called primitive roots; a is a primitive root if a is a number prime to a number p, then at ≡ 1 is true for no number less than p-1. There is a very restricted class of numbers that have this property. But if every number less than a given number is a primitive root, then that number is a prime.
1thanx prophet i always enjoy reading your posts btw don't reply to such nonsense posts unless you have free time
you know i wasn't seriously looking for such a prompt answer to something not in course.
62phew... woow
din know this!! ...
good one prophet....
I am amazed to see ur depth of knowledge in mathematics....
Well done buddy....
1[11] talked all about fermat's last theorem without a word of the original statement
anyway here it is
Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et generaliter nullam in infinitum ultra quadratum potestatem in duos eiusdem nominis fas est dividere cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.
remembered only half of it so copy pasted [4]
11Guys, I'm suddenly seeing many of these "mod"s flying around. I also saw "congruence" in an arithmetic problem. What is this all about? [7][7][7]
13but bhaiya... its power raised to 500... i think v can't divide it directly...!!!