Re: Proof / counterexample requested

quasi wrote: 
On Mon, 02 Jan 2006 12:36:06 +0100, Marc Bogaerts
<mar_c.bo_gaerts@xxxxxxxxxxx> wrote:


Hi all,


Purely by chance I found out following hypothesis to be true for the few
hundreds of times I verified it by calculation. So I would like to know
if this is a corrollary to a known theorem/conjecture...


The hypothesis is the following:


Let n be a positive integer, and G the multiplicative group of integers mod n,
and let z be an element in G of prime order, then Gcd(z-1, n) <> 1.


Examples:


1) n=41*53
for z=42, 206, 452, 493, 1149, 1190, 1477, 1600, 1764, 1846, 2010 and 2133
we have that ord(z)=13, and Gcd(z-1, 41*53)=41;
for z=160, 584, 1697, 1846 and 2068 ord(z)=5 and Gcd(z-1, 41*53)=53;


2)n:=43*59
for z=87, 130, 302, 517, 560, 818, 861, 904, 947, 990, 1119, 1162, 1205,
1248, 1334, 1377,1420, 1549, 1678, 1764, 1850, 1893, 1936, 2022, 2151,
2323, 2409 and 2495 ord(z)=29 and Gcd(z-1, 43*59)=43;
for z=355, 532, 709, 1122, 1417, 1712 ord(z)=7 and Gcd(z-1, 43*59)=59:


If anyone could help me to find a proof (or a counterexample) of this
assertion,  I'd be very glad.



Counterexample: n=3, z=2, p=2

quasi

Agreed, but I admit to only have calculated this for n=p*q, where p and q are two odd primes (I was only interested in ways of factoring n).

It is clear that the hypothesis doesn't work if n is a prime, since z-1 < n and Gcd(n, z-1) is always 1.

The hypothesis should read

Let n be a positive composite integer (non prime), and G the multiplicative group of integers mod n,
and let z be an element in G of prime odd order, then Gcd(z-1, n) <> 1.

>
>
>



--
Remove underscores to retrieve email address.

.

Relevant Pages

  • Re: Proof / counterexample requested
    ... quasi wrote: ... hundreds of times I verified it by calculation. ... Let n be a positive integer, and G the multiplicative group of integers mod n, ...
    (sci.math)
  • Proof / counterexample requested
    ... hundreds of times I verified it by calculation. ... Let n be a positive integer, and G the multiplicative group of integers mod n, ... Remove underscores to retrieve email address. ...
    (sci.math)
  • Re: Proof / counterexample requested
    ... >>hundreds of times I verified it by calculation. ... >>Let n be a positive integer, and G the multiplicative group of integers ... here's another whole class of counterexamples ... ...
    (sci.math)
  • Re: Proof / counterexample requested
    ... quasi wrote: ... hundreds of times I verified it by calculation. ... Let n be a positive integer, and G the multiplicative group of integers mod n, ...
    (sci.math)
  • Re: Fermats Last Theorem
    ... Quote from quasi: ... Test a big positive integer for primality. ... references to old posts and copies of letters. ...
    (sci.math)