Question

Prove that a product logarithm function on a prime modulus can evaluate to all values

Answer 1

So for example product log base 3 takes the number multiplying and exponentiating the 3 and returns it, since that's just 4 there ya go. =)\[\LARGE W_3(4*3^4) \equiv 4 \mod 5\]

Answer 2

According to what I'm saying though, since 5 is prime, \[\LARGE W_3(4*3^4) \equiv 1 \equiv 2 \equiv 3 \equiv 4 \mod 5\] Now prove it's true in general for any a, n, and prime p: \[\LARGE W_n(a*n^a) \equiv 1 \equiv 2 \equiv \cdots \equiv p-1 \mod p\]

Answer 3

Following this

Answer 4

I'll give a little example of actually showing this while still in mod 5. \[\Large W_3(1*3^1) \equiv 1 \mod 5\] However since \[\Large 1*3^1 \equiv 3 + 5*3 \equiv 18 \mod 5 \\ \Large 18 \equiv 2*3^2 \mod 5\] then this also means \[\Large W_3(1*3^1) \equiv W_3(2*3^2) \equiv 2 \mod 5\]

Answer 5

Uhhh I guess I'll post the proof in about an hour if nobody's into it, but in the mean time I guess I'll give a more proper definition of it: \[\Large W_n(a*n^a) \equiv a \] And I'll go ahead and do another example of using it: So one weird way to calculate would be \[ \Large W_7(6) \equiv 2 \mod 11\] and the weird calculation goes as follows: \[\Large W_7(6) \equiv W_7(24*7^{24}) \equiv 24 \equiv 2 \mod 11 \]

Answer 6

\[
W_7(6)= x \iff x(7)^x=6 \implies x\approx 0.948\ldots
\]I don't see the sense in performing a modulus operation on this number.

Answer 7

Are you saying that it's only the integer solutions modulus some number?

Answer 8

Yeah, I'm only working with integers here. So it's a discrete product log I guess you could say it that way.

Answer 9

How did you get from \(6\) to \(24(7)^{24}\)?

Answer 10

Kind of like how you can define a discrete square root in modular arithmetic, since \[\Large 3^2 \equiv 3 \mod 6\] we can say \[\Large 3 \equiv \sqrt{3} \mod 6\] as long as we understand what is meant.

Answer 11

Oh because 24*7^24 mod 11 is also 6. Of course this is just one representation of 6 in mod 11 that fit into the form of a*n^a http://www.wolframalpha.com/input/?i=24*7%5E24%20mod%2011&t=crmtb01

Answer 12

Okay, so mod \(11\) was just another given variable or what?

Answer 13

Well, basically I guess, I'm not entirely sure I understand you. The product log doesn't itself depend on the mod, but in modular arithmetic it allows us to just add or subtract multiples of it to the numbers as usual.

So like in this example above, \[\Large W_3(1*3^1) \equiv 1 \mod 5\] We can make use of the mod 5 to change 1*3^1 into 2*3^2 since they are a multiple of 5 apart. \[\Large 1*3^1 \equiv 3 + 5*3 \equiv 18 \mod 5 \\ \Large 18 \equiv 2*3^2 \mod 5\] and when we evaluate it this way, it ends up being multivalued. This is true for all prime modulus, however for nonprime modulus it seems to be that it ends up being single valued (not sure, haven't figured that out completely yet) \[\Large W_3(1*3^1) \equiv W_3(2*3^2) \equiv 2 \mod 5\]

Answer 14

for a fixed integer \(n\) and prime \(p\), we want to test the solvablity of below congruence
\[\large xn^x\equiv c \pmod {p}\]

?

Answer 15

I'm not sure, but I don't think that's exactly an equivalent statement, I'm thinking about it though so I'll say in a minute or two if I can figure that out.

Answer 16

In above congruence, as per your definition of discrete product log, \(W_n(c) = x\)

Answer 17

Well the way you've written it is sort of confusing to me since it's sort of harder to phrase this way I think, but I'll give it a shot:

So in mod 5 so if we look at 1,2,3,4 we can always find a way to represent \[\Large xn^x \equiv c \mod 5\] with fixed n and c where x is congruent to each of those... A concrete example is: \[\Large 1*3^1 \equiv 3 \mod 5 \\ \Large 2*3^2 \equiv 3 \mod 5 \\ \Large 8*3^8 \equiv 3 \mod 5 \\ \Large 19*3^{19} \equiv 3 \mod 5\] since \[\Large 8 \equiv 3 \mod 5 \\ \Large 19 \equiv 4 \mod 5\] we have shown that we can represent for n=3 and c=3 that we can use any value in mod 5 to complete the statement. Without the logarithm the statement of this seems off to me since although 19 works because it's 4 mod 5, 4*3^4 itself does not work.

Answer 18

\(c\) is not fixed in above congruence

Answer 19

we want to see if a solution exists for above congruence by varying \(c\) in modulo \(p\)

Answer 20

Well I have just shown that all of the values less than p evaluate to a fixed c. If you show this is true for all c then you've shown exactly what you're saying right?

Answer 21

4*3^4 doesnt work
but 19*3^19 works

how is this causing any harm ?

Answer 22

\(a\equiv b \pmod n\) need not imply \(x^a \equiv x^b \pmod n\)

Answer 23

It doesn't? I'm just saying it makes it hard for me to think about it when it's not in the logarithm form lol.

Answer 24

Right, I agree with you.

Answer 25

it is okay to say \(W_3(3) = 1,2,8,19\) because we're talking about exponents here and exponent don't reduce in moduli in general

Answer 26

im not so sure i fully get the question... but the congruence i put above is easy to test

Answer 27

Right, so I'm saying it's not ok to write them as that, I'm putting the constraint on that \(W_3(3) = 1,2,3,4 \mod 5\) and extending it to say \[W_n(r) = 1,2,3,.. , p-1 \mod p\] for all r and all n

Haha I guess the hardest part of this question I'm asking is figuring out what the heck I'm saying.

Answer 28

so \(xn^x \equiv c \pmod{p}\)
with a constraint that \(x\lt p\) ?

Answer 29

as you can see im trying to decouple the product log part and translate the problem to a pure congruene solving problem

Answer 30

I think that sounds right. Slight thing to mention is x doesn't really have an upper limit on it, it's just that if x>p you will be able to subtract p off of it until it is.

Answer 31

you cant subtract p off of x when x is an expoentn

Answer 32

I'm saying you can.

Answer 33

I just gave you permission.

Answer 34

that doesn't work

Answer 35

Why not?

Answer 36

a=bmod p need not imply x^a = x^b mod p

subtracting business wont work with exponent

Answer 37

Yeah, I completely agree with you.

Answer 38

For a fixed \(n\) and odd prime \(p\), we want to test the solvability of \[xn^x \equiv c \pmod{p}\]
with a constraint that \(1\le x\lt p\)

is this correct representation of the problem ?

Answer 39

I'm not sure, what's your doubt?

Answer 40

\[\Large 3 \equiv1*3^1 \equiv 1*3^1+5*3 \equiv 2*3^2 \mod 5\] This is a fact, so we can show that we are able to evaluate it ambiguously \[\Large W_3(3) \equiv 1 \mod 5\\ \Large W_3(3) \equiv 2 \mod 5\] Now I'm saying that for any prime modulus it will be ambiguous in that any number at any other base can evaluate to every single number in that modulus.

Answer 41

im asking whether above congruence is correct representation of your problem or not

Answer 42

I am just not really able to wrap my mind around if what you're saying is equivalent to what I'm saying or not.

Answer 43

same here

Answer 44

transitive property works when the variable is not in the expoennt, you can't simply give permission to remove p from x when x is in exponent

that part is throwing me off

Answer 45

Oh wait a sec i think i see whats going on

Answer 46

I was going to say, make sure you are accepting that this statement is true... The product log is DEFINITELY multivalued. \[\Large W_n(a) \equiv W_n(a+p) \mod p \]

Answer 47

can we remove that product log wrapper and talk in terms of congruences ?

Answer 48

I guess that statement might seem fairly ambiguous... because although the insides are equivalent the values they spit out AREN'T but I'm saying that's how it works.

Answer 49

because idk fully how that beast works..

Answer 50

Yes exactly, the inside can be moved around as a congruence and the outsides can be moved around as congruences.

Answer 51

The problem is this causes it to be multivalued... And I'm saying prove that this animal takes on ALL values for a prime modulus... Maybe that helps?

Answer 52

let me work \(W_3(a) \) in modulus 11

Answer 53

you're sayign it can evaluate to all residues : {1 .. 10} right ?

Answer 54

Yeah exactly, by adding multiples of 11 to a you can get all residues.

Answer 55

Which is basically cause of what you were saying earlier about there being "no connection" between exponents and stuff. There's sort of actually an interesting connection going on imo.

Answer 56

there is a connection, what i was saying earlier is that you cant simply remove p from x

Answer 57

to evaluate \(W_3(a)\) do we work
\[x3^x \equiv a\pmod{11}\]

Answer 58

is that ur definition of discrete product log ?

Answer 59

\[W_3(1*3^1) \equiv 1 \mod 11 \\ W_3(2*3^2) \equiv 2 \mod 11 \\ W_3(3*3^3) \equiv 3 \mod 11 \\ W_3(4*3^4) \equiv 4 \mod 11 \\ W_3(5*3^5) \equiv 5 \mod 11 \\ W_3(6*3^6) \equiv 6 \mod 11 \\ W_3(7*3^7) \equiv 7 \mod 11 \\ W_3(8*3^8) \equiv 8 \mod 11 \\ W_3(9*3^9) \equiv 9 \mod 11 \\ W_3(10*3^10) \equiv 10 \mod 11 \\ W_3(11*3^11) \equiv 11 \mod 11 \\ W_3(12*3^12) \equiv 12 \mod 11 \\ W_3(13*3^13) \equiv 13 \mod 11 \\ W_3(14*3^14) \equiv 14 \mod 11 \\ W_3(15*3^15) \equiv 15 \mod 11 \\ W_3(16*3^16) \equiv 16 \mod 11 \\ W_3(17*3^17) \equiv 17 \mod 11 \\ W_3(18*3^18) \equiv 18 \mod 11 \\ W_3(19*3^19) \equiv 19 \mod 11 \\ \] etcetera I guess I made the program run too far but too late now haha.

Answer 60

I fixed it a bit to show that larger than 10 it changes... I'm not sure if this helps, but I am defining it completely on taking the exponent and multiplier when they're identical. Uhhh... lol it is what it is, I don't know what else to say really \[W_3(4*3^4) \equiv 4 \mod 11 \\ W_3(5*3^5) \equiv 5 \mod 11 \\ W_3(6*3^6) \equiv 6 \mod 11 \\ W_3(7*3^7) \equiv 7 \mod 11 \\ W_3(8*3^8) \equiv 8 \mod 11 \\ W_3(9*3^9) \equiv 9 \mod 11 \\ W_3(10*3^10) \equiv 10 \mod 11 \\ W_3(11*3^11) \equiv 0 \mod 11 \\ W_3(12*3^12) \equiv 1 \mod 11 \\ W_3(13*3^13) \equiv 2 \mod 11 \\ W_3(14*3^14) \equiv 3 \mod 11 \\ W_3(15*3^15) \equiv 4 \mod 11 \\ W_3(16*3^16) \equiv 5 \mod 11 \\ W_3(17*3^17) \equiv 6 \mod 11 \\ W_3(18*3^18) \equiv 7 \mod 11 \\ W_3(19*3^19) \equiv 8 \mod 11 \\\]

Answer 61

Don't let your desire for "exponents don't do this or that!" to get in the way. It's just like this, even if it seems bad, that's just how it goes. We can look at the congruence after evaluating it and before evaluating it.

Haha maybe I should just show my proof and get over this since I'm really only proving this as a mild curiosity before evaluating the product log in composite moduli which is what I'm really interested in...

Answer 62

i wish you good luck... honsestly i don't get the problem statement itself but this isn't the first time i couldnt comprehend ur weird stuff lol

Answer 63

Haha well the proof is fairly straightforward, it involves Fermat's little theorem and maybe that'll help.

Let's consider ourselves in mod p, where p is prime and we'll pick an arbitrary integer a and n to consider:

$$W_n(an^a) \equiv a \mod p $$

Now we know $a \equiv a+p \mod p$ So let's substitute it into the product log

$$W_n((a+p)n^{a+p}) \equiv a \mod p$$

Now let's manipulate the inside

$$W_n(an^{a+p} +pn^{a+p}) \equiv W_n(an^aa^p) \mod p$$

Since $n^{a+p}$ multiplies p, it is not part of the remainder in mod p and we remove it, now we appeal to Fermat's little theorem and replace $a^p \equiv a \mod p$

$$W_n(an^a *n) \equiv a \mod p$$

So now we are in a place to see how the product log is not unique. We have really shown that

$$W_n(an^a) \equiv W_n(an^a*n) \mod p$$

So if we replace $an^a = b$ it becomes more clear:

$$W_n(b) \equiv W_n(b*n) \mod p$$

We could continually do this process of finding different values that evaluate to a in mod p by simply multiplying our starting number b by n, or simply by n raised to an arbitrary integer power, let's use x. In our prime modulus we know that all possible values of b are generators of the cycle, so this means that $b*n^x \mod p$ can take on all values! So to state a little more clearly:

$$W_n(an^a * n^x) \equiv W_n(anything!) \equiv a \mod p$$

So we have effectively shown that all values can evaluate to any value we want in a prime modulus, and since this is true for any a, that's the end of the proof...!

Answer 64

Now what I'm more interested in is composite modulus since it seems to be single valued. A quick example is: \[\Large W_5(a*5^a) \equiv a \mod 6\] It seems apparent that the only values that will give us a are a plus a multiple of 6.\[\Large a \equiv a+6 \equiv a+12 \equiv a+m6 \mod 6\] So if we plug in a+m6 into our equation we get: \[\Large W_5((a+6m)5^{a+6m})\equiv a \mod 6\] We can simplify the inside to \[\Large W_5(a5^a5^{6m})\equiv a \mod 6\] But instead of Fermat's little theorem like we did in the proof, we instead note that \[\Large 5^2 \equiv 1 \mod 6\] and we safely replace it to get \[\Large W_5((a+6m)5^{a+6m}) \equiv W_5(a5^a) \equiv a \mod 6\] which means it's not ambiguous since all possible values evaluate to the same value.