Fermat's Theorem

[pkothari13]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#1

Fermat's Theorem

[Rep123max]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#2

Ya, that is Euler's (I believe) extension of it, the original theorem is where p is prime and a is not a multiple of p.

Some examples I guess would be: What is the remainder when is divided by 17? That is off the top of my head so if it comes out to be a big number, don't blame me!

I'm actually blanking on more thinking type questions, but when I think of some, I'll post em.

[towersfreak2006]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#3

Perhaps both of you remember this one?

Reduce to an equivalent polynomial with lowest positive exponents.

[pkothari13]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#4

[JBL]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#5

Not "you can assume it" -- by Fermat's Little Theorem, we know that .

Also, Towersfreak, I assume you want x integral, right?

[Rep123max]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#6

Oh ya, I do remember that. ARML packet from Richardson tests (which my current teacher wrote, I wish we did problems like that in class instead of the monotonous problems we do now).

[pkothari13]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#7

I was looking through some old problems and saw the formula could be applied to finding the units or tens or hundreds, etc digit of a number such as 9^357. But.. I'm still kinda lost .

[Gyan]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#8

Okay here is an old problem from 1978
if last three digits of is same as the last three digits of find m and n such that m+n is minimum.
(m,n are natural numbers and m is not equal to n that is )

[Gyan]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#9

[pkothari13]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#10

[JBL]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#11

[Gyan]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#12

[Gyan]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#13

[pkothari13]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#14

[JBL]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#15

hrm? Why every 4?

[Elemennop]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#16

The original theorem (Euler's phi theorem) is used (or at least I use) very often for problems asking to find the last x digits of an enormous number.

Ex. What is the last two digits of 3^843?

[TripleM]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#17

[NightFlarer]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#18

so since a^(p-1) = 1 (mod p), we have a^6 = 1 (mod 7)
in this case we have x not a, so for 3x^23 we have

3((x^6)^3 * x^5)
3(1*x^5)
3(x^5)

then we have 2x^19, which is just 2x
next is 7x^14, isn't this 0 mod 7 anyway because of the 7? can't we just get rid of it? anyway, doing the same as before we would have 7x^2

lastly, -2x^6 = -2

so we have

3x^5 + 2x + 7x^2 -2 (mod 7)

I hope this is right

actually...couldn't we say 3x^5 = 3x^6 * x^-1?
because then we have 3/x...

so I guess it's 3/x + 2x + 7x^2 -2 (mod 7) or 7x^2 + 2x + 3/x -2 (mod 7)


And as for you mister pkothari, you need to pick it up! You weren't featured in that magazine for nothing! (Perhaps you remember me from the Dulles competition a month or two ago...) Just kidding, of course

[JBL]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#19

Good work, but one problem: your next-to-last step (with the x^6 term) is not absolutely true: x^6 = 1 (mod 7) only when x is not divisible by 7. This is why I prefer a different statement of Fermat's Little Theorem: for all primes p and integers a.