NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/sci/math/11420

Text File | 1992-09-14 | 1.6 KB | 38 lines

Newsgroups: sci.math
Path: sparky!uunet!elroy.jpl.nasa.gov!sdd.hp.com!ux1.cso.uiuc.edu!usenet.ucs.indiana.edu!newshost.cs.rose-hulman.edu!news
From: [e-mail] (Bart Goddard)
Subject: Re: The Last Number Theory Problem
Message-ID: <[e-mail]>
Sender: [e-mail] (The News Administrator)
Nntp-Posting-Host: g214-1.nextwork.rose-hulman.edu
Organization: Rose-Hulman Institute of Technology
References: <[e-mail]>
Date: Mon, 14 Sep 1992 17:29:21 GMT
Lines: 25


In article <[e-mail]> I wrote:
>
> 5.2.11.a (Solved) Show that if n is a pseudoprime to the base a but
> not a pseudoprime to the base b, where (a,n)=(b,n)=1, then n is not a
> pseudoprime to the base ab.
>
> 5.2.11.b Show that if there is an integer b with (b,n)=1 such that n
> is not a pseudoprime to the base b, then n is a pseudoprime to <=
>\phi(n) different bases a, with 1<=a<n.  (Hint: Show that the sets
>a_1, a_2, ..., a_r, and ba_1, ba_2,...,ba_r have no common elements,
>where a_1, a_2, ..., a_r, are the bases less than n to which n is a
>pseudoprime.)

I have received a couple of solutions, but I need to clarify something:
In this text, a pseudoprime need not be relatively prime to the base,
the only requirement is that a^n == a (mod n).  So we need to
either solve the problem under this condition, or assume that (a,n)=1
for every base a (in which case we use \phi(n)/2 and the problem is
trivial.)

Come to think of it, I'd bet on the latter case....but just in case...

Bart Goddard
[e-mail]