Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Replies: 54   Last Post: May 6, 2002 11:25 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Nico Benschop

Posts: 1,708
Registered: 12/6/04
Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Posted: Apr 30, 2002 1:59 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



Joe Number <n@ion.isotope> wrote
>
> Nico Benschop <n.benschop@chello.nl> wrote:
>

> >> a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c< p)
> >> does have solutions, and normalize to c = p-1

>
> Sorry I don't have the info. Why can't your PC handle larger p?
> What sort of PC do you think could handle the problem? It does
> not look like it should require much memory or much speed.


It's just that higher precision, say 64 bits or more, is needed for
arithmetic mod p^4 at the parger primes p, say p>10^4. Complete
search for a+b=p-1, with a<(p-1)/2, grows quadratically with p,
so full search requires a rather powerful machine, if no counter
example is found early on, for smallish p.

> It seems to me if you normalize c to p-1 modulo p^k, you will
> change the values of a and b so that if a, b, c < p then
> a and b might become > p. That is, if normalize means what
> I think it means.


Well, if they were integers you would be right, but they are
residues (mod p^k). For instance [1] has all terms coprime to p,
so they are in the (cyclic) group of units, so each residue
has a unique inverse so that [1] can be multiplied throughout by
the inverse of one of the terms to make it == 1 mod p^k, or here:
divide by -c^p to get normal form x^p + y^p == -1 mod p^k,
or: a 'scale factor' that makes r^p + s^p == (p-1)^p mod p^k.
considering only pos.integers 0 < r, s, p-1 < p

> I read some of the things at your site, and I thought it was
> interesting as far as I could understand it. But I am a genuine
> amateur and it is a bit complex and the meaning is often unclear.
> For instance, what does "core" mean?


I use the simplest principles of residue arithmetic mod p^k
(odd prime p), which Fermat around 1640 discovered for case k=1:
Fermat Small Thm (FST): n^p == n mod p (odd prime p, all n).

And residue arithmetic was formalized in general by Gauss (1801),
as satisfying the same syntax rules as integer arithmetic:
associative and commutative (+) and (.)
(.) distributes over (+), and (^) over (.), but (^) not over (+)

> For instance, what does "core" mean?

There are p^{k-1} residues mod p^k which are a multiple of p,
hence 0 mod p, and the same number of residues that are 1 mod p.

All p^k - p^{k-1} = (p-1)p^{k-1} residues mod p^k coprime to p
are called 'units' (mod p^k), and they form a cyclic group: one
generator suffices to get G_k == \{ g^i \} for i=1 .. (p-1)p^{k-1}.

This product order of two coprime factors makes G_k == A_k . B_k,
where 'core' A_k has order p-1 (note: an extention of FST for k>1),
and 'extension group' B_k has order p^{k-1}, generated by p+1,
so B_k == \{ (p+1)^i, for all i=1 .. p^{k-1} \},
consisting of all residues mod p^k that are 1 mod p.
With G_k being cyclic, also factor groups A_k and B_k are cyclic.

And in cyclic group A_k(.) of order p-1 holds:
n^p == n for all n in A_k (i.e. for each core residue n).

Re: FLT for integers .vs. for residues mod p^k:
Each solution of: a^p + b^p == c^p "in core" A_k has:

a^p==a, b^p==b and c^p == (a+b)^p == a+b == a^p + b^p (mod p^k)

Hence: exponent p distributes over a sum (EDS property)
which "blocks extension to integers", meaning:
integers A,B,C with A^p==a^p, B^p==b^p, C^p==c^p (mod p^k)
cannot exist [since EDS does not hold for integers].

> Caeo, Nico
>
> PS: Hey, are you Italian, Dutch, or English?


I'm Dutch (see CV on my homepage;-)
I just, sometimes, use Ciao for fun.

-- NB - http://home.iae.nl/users/benschop/scimat98.htm
http://home.iae.nl/users/benschop/sgrp-flt.htm
http://home.iae.nl/users/benschop/carry.htm






Date Subject Author
4/23/02
Read Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Nico Benschop
4/23/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Nico Benschop
4/23/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Nico Benschop
4/27/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Joe Number
4/29/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c< p)
Nico Benschop
4/30/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Nico Benschop
5/3/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Joe Number
5/3/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Joe Number
5/4/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Joe Number
5/5/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Nico Benschop
5/6/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Joe Number
4/23/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Robin Chapman
4/24/02
Read Re: Can a^p + b^p == c^p mod p^k (odd prime p, 0<a,b,c<p) ?
Nico Benschop
4/24/02
Read more NFB garbage
Robin Chapman
4/24/02
Read Re: more NFB garbage, and RC insults
Nico Benschop
4/24/02
Read Re: more NFB garbage, and RC insults
David C. Ullrich
4/24/02
Read Re: more NFB garbage
Robin Chapman
4/24/02
Read Re: more NFB garbage
Nico Benschop
4/24/02
Read Re: more NFB garbage
Robin Chapman
4/24/02
Read Re: more NFB garbage
Nico Benschop
4/24/02
Read Re: more NFB garbage
Pertti Lounesto
4/25/02
Read Re: more NFB garbage
Nico Benschop
4/27/02
Read Re: more NFB garbage
Robin Chapman
4/28/02
Read Re: more NFB garbage [was: Can a^p + b^p == c^p mod p^k (odd prime p,
0<a,b,c<p) ?]
Nico Benschop
4/28/02
Read Re: more NFB garbage
Robin Chapman
4/25/02
Read Re: more NFB garbage
Robin Chapman
4/25/02
Read Re: more NFB garbage
Nico Benschop
4/25/02
Read Re: more NFB garbage
Robin Chapman
4/25/02
Read Re: more NFB garbage
Pertti Lounesto
4/25/02
Read Re: more NFB garbage
Pertti Lounesto
4/25/02
Read Re: more NFB garbage
Pertti Lounesto
4/26/02
Read Re: more NFB garbage
Nico Benschop
4/27/02
Read Re: more NFB garbage
Robin Chapman
4/27/02
Read Re: more NFB garbage
Pertti Lounesto
4/28/02
Read Re: more NFB garbage
Pertti Lounesto
4/29/02
Read Re: more NFB garbage
Pertti Lounesto
4/29/02
Read Re: more NFB garbage
Nico Benschop
4/30/02
Read Re: more NFB garbage
Pertti Lounesto
4/30/02
Read Re: more NFB garbage
Nico Benschop
5/1/02
Read Re: more NFB garbage
Pertti Lounesto
5/1/02
Read Re: more NFB garbage
Denis Feldmann
5/1/02
Read Re: more NFB garbage
Pertti Lounesto
5/1/02
Read Re: more NFB garbage
Denis Feldmann
5/1/02
Read Re: more NFB garbage
Pertti Lounesto
5/1/02
Read Re: more NFB garbage
Nico Benschop
5/1/02
Read Re: more NFB garbage
Nico Benschop
5/2/02
Read Re: more NFB garbage
Pertti Lounesto
5/2/02
Read Re: more NFB garbage
Robin Chapman
5/1/02
Read Re: more NFB garbage
Robin Chapman
5/1/02
Read Re: more NFB garbage
Pertti Lounesto
5/2/02
Read Re: more NFB garbage
Robin Chapman
4/26/02
Read Re: more NFB garbage
Nico Benschop
4/26/02
Read Re: more NFB garbage
Nico Benschop
4/26/02
Read cancel <3CC9123E.E8876954@chello.nl>
Nico Benschop
4/26/02
Read Re: more NFB garbage
Nico Benschop

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.