Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 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

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 Nico Benschop
4/23/02 Nico Benschop
4/23/02 Nico Benschop
4/27/02 Joe Number
4/29/02 Nico Benschop
4/30/02 Nico Benschop
5/3/02 Joe Number
5/3/02 Joe Number
5/4/02 Joe Number
5/5/02 Nico Benschop
5/6/02 Joe Number
4/23/02 Robin Chapman
4/24/02 Nico Benschop
4/24/02 Robin Chapman
4/24/02 Nico Benschop
4/24/02 David C. Ullrich
4/24/02 Robin Chapman
4/24/02 Nico Benschop
4/24/02 Robin Chapman
4/24/02 Nico Benschop
4/24/02 Pertti Lounesto
4/25/02 Nico Benschop
4/27/02 Robin Chapman
4/28/02 Nico Benschop
4/28/02 Robin Chapman
4/25/02 Robin Chapman
4/25/02 Nico Benschop
4/25/02 Robin Chapman
4/25/02 Pertti Lounesto
4/25/02 Pertti Lounesto
4/25/02 Pertti Lounesto
4/26/02 Nico Benschop
4/27/02 Robin Chapman
4/27/02 Pertti Lounesto
4/28/02 Pertti Lounesto
4/29/02 Pertti Lounesto
4/29/02 Nico Benschop
4/30/02 Pertti Lounesto
4/30/02 Nico Benschop
5/1/02 Pertti Lounesto
5/1/02 Denis Feldmann
5/1/02 Pertti Lounesto
5/1/02 Denis Feldmann
5/1/02 Pertti Lounesto
5/1/02 Nico Benschop
5/1/02 Nico Benschop
5/2/02 Pertti Lounesto
5/2/02 Robin Chapman
5/1/02 Robin Chapman
5/1/02 Pertti Lounesto
5/2/02 Robin Chapman
4/26/02 Nico Benschop
4/26/02 Nico Benschop
4/26/02 Nico Benschop
4/26/02 Nico Benschop