Fermat Theorem Puzzle
Source: Andrej Cherkaev's List of Puzzles
Problem:
A computer scientist claims that he proved somehow that the Fermat theorem is correct for the following 3 numbers:
x=2233445566,
y=7788990011,
z=9988776655
He announces these 3 numbers and calls for a press conference where he is going to present the value of N (to show that
x^N + y^N = z^N
and that the guy from Princeton was wrong). As the press conference starts, a 10-years old boy raises his hand and says that the respectable scientist has made a mistake and the Fermat theorem cannot hold for those 3 numbers. The scientist checks his computer calculations and finds a bug.
How did the boy figure out that the scientist was wrong?
Update (06/01/2012):
Solution posted by a lot of people in comments!
By last digit number? Or is it even easier than that?
ReplyDeleteAny power of x = 2233445566 must end with the digit 6 and any power of y = 7788990011 must end with the digit 1. Further, any power of z must also end with 5. Hence, x^N + y^N can not be equal to z^N for any value of N.
ReplyDeletelast digit of x^n + y^ n = 7, and last digit of z^n = 5.
ReplyDeletex^n for any value of n will always have the least significant digit as 6, similarly y^n for any value of n will always end with 1 , and hence there sum will always end with the least significant digit as 7 , whereas z^n will always have 5 as the least significant digit.
ReplyDeletewhatever the value of N ,x^N will always end with 6(one's place) and. y^N will end with 1. so there sum can never give number with a one's digit equal to 5 (which will always be the case for z^N)
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteClaim:
ReplyDeletexxxxx6^N = 6 mod 10 for all N
xxxxx1^N = 1 mod 10 for all N
xxxxx5^N = 5 mod 10 for all N
Proof:
By induction
Let us suppose xxxx6^(N-1) = 6 mod 10
xxxxx6 = 6 mod 10
Thus xxxx6^N = 6*6 mod 10 = 6 mod 10
Similarly, the claim can be proved for the other two cases.
if xxxx6^N + xxxxx1^N = xxxxx5^N
then xxxx6^N % 10 + xxxxx1^N % 10 = xxxxx5^N % 10 which is a contradiction from the above claim
Any power of x ends with a 6, that of y ends with a 1 and that of z ends with 5 . Thus x^n +y^n ends with 7 while z^n ends with 5. This proves that the scientist was wrong
ReplyDeleteThe units digit of x^N is 6, of y^N is 1, and of z^N is 5. [*]
ReplyDeleteThe units digit of x^N + y^N is therefore 7. Given what we know about the units digit of z^N, the scientist must therefore be wrong.
[*] Consider (10a+6)² = (100a² + 20a + 36) and apply in an inductive proof. Same method for (10a+5) and (10a+1).
x^anything will end with 6, y^anything will end with 1. So their sum should end with 7. z^anything should end with 5.
ReplyDeleteThis one's seems easy.
ReplyDeleteSince units digit of x is 6, the units digit of x^n will be 6 irrespective of the value of n.
Similarly units place of y^n will always be 1 and that of z^n will always be 5.
So the units digit of LHS is 7 and that of RHS is 5. Clear mismatch.
Hence that boy could prove the great scientist wrong using just simple school maths !!
we can see that the equality can't hold by observing the equality mod 10. x^N % 10 = 6 y^N%10 = 1 and z^N%10 = 5 always.
ReplyDeleteUm, you mean that the scientist claims to have a *counterexample* to Fermat's Last Theorem. I'll keep quiet about the solution.
ReplyDeleteDoes not even work for N=1
ReplyDeleteCan you please provide the source please?
ReplyDeleteThis comment has been removed by the author.
ReplyDelete6^n always ends in a 6.. 1^n always ends in a 1 .. and 5^n always ends in a 5..
ReplyDeleteWith the given numbers .. x^n+y^n must end in 7 ..
Hence, there is surely some mistake ..
x ^ N mod 10 = 1
ReplyDeletey ^ N mod 10 = 6
and
z ^ N mod 10 = 5
So equation will never hold modulo 10
shouldn't x^N+y^N = 7 mod 10 ?
ReplyDeletehint: any power of a number ending in 6 will always end in 6.
ReplyDeleteWith following argument :
ReplyDelete-> every exponent of x has unit digit 6
-> every exponent of y has unit digit 1
so (x^N + y^N) will have unit digit 7
-> but every exponent of z has unit digit 5
@Ameya, @Anirudh Kumar, @Siddhartha, @donotevenbother, @iron feliks, @vivek ranjan nema, @napster, @aditya_iitr, @JDGM, @Vivek, @amit yadav, @rishabh, @r, @akhil, @piyush, @bob, @shubham.. Thanks for the correct solution :-)
ReplyDelete@andrew milne..
x+y>z, but x^n + y^n can be equal to z^n. The scientist has to come up with the number n. To disprove Fermat's last theorem, you had to provide that there exists a 'N'
@ravi. source is already provided
@as. The scientist has to come up with the number n. To disprove Fermat's last theorem, you had to provide that there exists a 'N'
Based on the example x+y > z. So there doesn't exist any N>2. ( P.S. I get the essence of question )
ReplyDeleteHere is a different solution:
ReplyDeletex is 1 mod 3, y is -1 mod 3. So x^n + y^n will always be either 0 mod 3 or 2 mod 3.
However, z is 1 mod 3, and hence z^n is always 1 mod 3.
cool. thanks
Deleteclearly, it doesn't work for N=1. Now for N>1 and given X and Y, we have
DeleteX^N > X ; Y^N>Y => X^N+Y^N = Z > X+Y;
thus Z > 10022435577 for all N >1 ; The scientist provides Z as 9988776655 which clearly violates this. Thus by simple 10 yr old logic, the scientist was wronged.
Kunal, the equation is X^N+Y^N = Z^N and not X^N+Y^N = Z
Delete