Prev: Is JAA (from Heldermann-Verlag) still alive ?
Next: meami, by the cheat and liar musatov
From: Pubkeybreaker on 6 Apr 2010 11:20
On Apr 6, 10:58 am, recoder <kurtulmeh...(a)gmail.com> wrote:
> On 6 Nisan, 17:11, Chip Eastham <hardm...(a)gmail.com> wrote:
>
>
>
>
>
> > On Apr 6, 9:52 am, Dan <dbri...(a)mit.edu> wrote:
>
> > > On Apr 6, 9:27 am, recoder <kurtulmeh...(a)gmail.com> wrote:
>
> > > > I need to find  what x would be in 3^x = 1 mod (p) where p is a prime?
> > > > Can we express x in terms of p?
>
> > > > Thanks in advance...
>
> > > x = 0 (mod p-1) gives a subset of the set of all solutions, by
> > > Fermat's Little Theorem.
>
> > > There's a conjecture that x = 0 (mod p-1) gives the full set of
> > > solutions for infinitely many (but nevertheless, not that many) p:
> > >http://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots
>
> > Consider for example 3^x = 1 mod 7.
> > Per Fermat's Little Theorem,
> > 3^6 = 1 mod 7, and in fact x = 6 is
> > the smallest positive integer solution.
>
> > However 3^7 = 1 mod 1093, showing that
> > as Dan implies above, the smallest
> > exponent can be a proper divisor of p-1.
>
> > regards, chip
>
> Thanks a lot. I wonder if there is a solution for 3^x = y mod (p)
> where y= 2^z and z is integer.- Hide quoted text -

Only if y is in 3's orbit.
From: Chip Eastham on 6 Apr 2010 11:52
On Apr 6, 10:58 am, recoder <kurtulmeh...(a)gmail.com> wrote:
> On 6 Nisan, 17:11, Chip Eastham <hardm...(a)gmail.com> wrote:
>
>
>
>
>
> > On Apr 6, 9:52 am, Dan <dbri...(a)mit.edu> wrote:
>
> > > On Apr 6, 9:27 am, recoder <kurtulmeh...(a)gmail.com> wrote:
>
> > > > I need to find  what x would be in 3^x = 1 mod (p) where p is a prime?
> > > > Can we express x in terms of p?
>
> > > > Thanks in advance...
>
> > > x = 0 (mod p-1) gives a subset of the set of all solutions, by
> > > Fermat's Little Theorem.
>
> > > There's a conjecture that x = 0 (mod p-1) gives the full set of
> > > solutions for infinitely many (but nevertheless, not that many) p:
> > >http://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots
>
> > Consider for example 3^x = 1 mod 7.
> > Per Fermat's Little Theorem,
> > 3^6 = 1 mod 7, and in fact x = 6 is
> > the smallest positive integer solution.
>
> > However 3^7 = 1 mod 1093, showing that
> > as Dan implies above, the smallest
> > exponent can be a proper divisor of p-1.
>
> > regards, chip
>
> Thanks a lot. I wonder if there is a solution for 3^x = y mod (p)
> where y= 2^z and z is integer.

It's a standard result of elementary number
theory that the field Z/pZ (p prime) has a
cyclic multiplicative group (the group of
all nonzero residues with respect to the
field multiplication). Any generator of
this group is called a "primitive" element.

The Artin conjecture on primitive roots
that Dan pointed you to early says (in a
particular case) that 3 should be primitive
for infinitely many 3, in which case
3^x = y mod p will have a solution, whatever
y happens to be (other than zero). [You
ask about y an integral power of 2.]

If you pick a prime modulus p where 2 is
primitive but 3 is not, then there will
not be solutions for 3^x = 2 mod p. One
such prime modulus is p = 13, where 2 has
order 12 in the multiplicative group but
3 only has order 3 (3^3 = 1 mod 13).

regards, chip
First  |  Prev  | 
Pages: 1 2
Prev: Is JAA (from Heldermann-Verlag) still alive ?
Next: meami, by the cheat and liar musatov