Re: euler's phi-function and divisibility by primes

Am 10.05.2006 16:51 schrieb Arturo Magidin:

I've difficulties to understand your example, I'm afraid.


Probably because I answered what you wrote, rather than what you
meant (judging from below and your other posts).

....
Now, if your confusion arises from the fact that this does not answer
what you MEANT to ask, well, forgive me, but "duh". I don't read

Oh, sorry; I did not intend to offend you, if that happend,
I beg your pardon as I already appreciate your offers of
help in so many other threads here araound.

No - what I did not understand was, why in

For example, take e=1, d=2, p=3; then phi(p^{e+1})=phi(3^2)=6. But if
a=2, then a^6 = 2^6 = 64, so a^6 - 1 = 63, which is not divisible by
p^{3}=27.

the p^{3}=27 occured, while you took as an example already
phi(p^{e+1}) = phi(3^2) and I expected a divisibilty argument
concerning phi(p^e)=phi(3^1) compared with phi(3^{e+1})=phi(3^2)
That means, I expected a divisibility argument like 3^2 = 9 or 3^1=3
related to 63 and not 3^3 = 27. So I said, I did not understand
your argument - I easily could have missed some other thought of yours.

I'm just answering immediate on receiving your post; I think at
a first read, that I catch up your example better now:

You asked whether it was always true that, for e>0 and d>1 and (a,p)=1,

p^{e+d} divides a^{phi^{e+1}} - 1.

And the answer is: no. In fact, you can find a single value of a for
which it will always fails: pick a primitive root g modulo p^2; it is
known that such a primitive root will be a primitive root modulo p^n
for any n>=2; hence the order of g modulo p^{e+d} will be
(p-1)p^{e+d-1}. Thus, plugging g for a, you can see that unless
e>=e+d-1, i.e., d<=1.


I think now, this

known that such a primitive root will be a primitive root modulo p^n
for any n>=2;

is the core argument, which was not known to me. So I can
follow the line now.


I picked p=3 and a=2 because 2 is a primitive root modulo 9. Then
3^{3}=p^{e+d} does NOT divides 64-1 = 2^{phi(p^{e+1})} - 1.

.... which confused me unfortunately, since it argues with (e+2) and
(e+1) where I was focused to find something about (e+1) and (e) having
still difficulties to fluently catch up arguments using primitive roots.
puhh...

Once more: sorry for that confusion.

Thanks -

Gottfried Helms

.

Relevant Pages

  • Re: eulers phi-function and divisibility by primes
    ... Gottfried Helms wrote: ... For any odd prime p, there are counterexamples (it will be true for ... pick a primitive root g modulo p^2; ... known that such a primitive root will be a primitive root modulo p^n ...
    (sci.math)
  • Re: eulers phi-function and divisibility by primes
    ... p^divides a^} - 1. ... pick a primitive root g modulo p^2; ... known that such a primitive root will be a primitive root modulo p^n ... Thus, plugging g for a, you can see that unless ...
    (sci.math)
  • Re: Primitive root
    ... You must also show that no smaller power of 3 is ... so 2 is not a primitive root. ... that a is a primitive root modulo m if and only if = 1 and the ... integer b, if =1, then there exists a positive integer n such ...
    (sci.math)
  • Re: related to group theory
    ... but 3 is not a generator surely. ... When n is either an odd prime power, twice an odd prime power, 2, or ... So, if you already know a primitive root, then it is very easy to find ... 2 is a primitive root modulo 10. ...
    (sci.math)
  • Re: Generator of a group
    ... >> all the quadratic residues modulo p and these ones are given by the ... > via finding a primitive root? ... What I wanted was to show to the OP the link between a generator ...
    (sci.crypt)