Anti Fermat's little theorem

True or false :

Because 1729 = 7 × 13 × 19 1729 = 7\times13\times19 is not a prime number , we can't apply Fermat's little theorem (FLT) to the following congruence:

2 1728 1 ( m o d 1729 ) . 2^{1728} \equiv 1 \pmod {1729}.

Because we can't apply FLT, the congruence above is incorrect.

True, the cogruence 2 1728 1 ( m o d 1729 ) 2^{1728} \equiv 1 \pmod {1729} is incorrect False, the congruence 2 1728 1 ( m o d 1729 ) 2^{1728} \equiv 1 \pmod {1729} is correct

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

We can apply fermat's little theorem to each of the prime divisors:- So we have 2 6 1 m o d 7 \displaystyle 2^{6}\equiv 1\mod7

2 12 1 m o d 13 \displaystyle 2^{12}\equiv 1 \mod 13

2 18 1 m o d 19 \displaystyle 2^{18}\equiv 1 \mod19

Thankfully we have 1728 1728 is divisible by all 6 6 , 12 \,12 and 18 18 .

So we have 2 1728 1 m o d 7 \displaystyle 2^{1728}\equiv 1 \mod7

2 1728 1 m o d 13 \displaystyle 2^{1728}\equiv 1 \mod13

2 1728 1 m o d 19 \displaystyle 2^{1728}\equiv 1 \mod19

So using Chinese Remainder Theorem :-

we have :-

2 1728 1 m o d 1729 \displaystyle 2^{1728}\equiv 1\mod1729

Note that You can also use Euler's division algorithm to easily see why the three simultaneous congruence relations give the answer as 1 mod 1729

See this wiki.

Atleast write 1729 is a Carmichael number.

Krutarth Patel - 5 years ago

Log in to reply

I have added the relevant wiki.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...