Register to reply 
Modulo and prime numbers 
Share this thread: 
#1
Nov412, 02:49 PM

P: 3

[tex]f(x)[/tex] will give us the smallest integer [tex]m[/tex] such that [tex]y^m \equiv 1 \bmod{x}[/tex] given that x and y are coprime
how would one go about showing that this function is multiplicative? I'm trying to do some Number Theory self study, and the problems I'm encountering are quite difficult to figure out from text alone. I'm guessing that the Chinese remainder theorem is applicable here. Also if we let p be prime then I know that f(p) will give the result of (p1). This is basically proved with Euler's theorem. Is this true or is Euler's theorem not so easily applicable here? I guess the fact that here m is the smallest integer, where's in Euler's it's not the smallest, but it's easy to prove that this doesn't matter using groups. 


#2
Nov912, 11:19 PM

Homework
Sci Advisor
HW Helper
Thanks
P: 9,839

How does y come in? Is it another given? If so, isn't it f(x, y)?



#3
Nov1012, 08:10 AM

P: 894




#4
Nov1012, 03:46 PM

Homework
Sci Advisor
HW Helper
Thanks
P: 9,839

Modulo and prime numbers



#5
Nov1012, 07:29 PM

P: 39

i don't think it's Euler's totient function.
for example, consider x = 37; y = 3. both prime, but the smallest m value is not 36, its 18. 


#6
Nov1012, 10:18 PM

Homework
Sci Advisor
HW Helper
Thanks
P: 9,839




#7
Nov1112, 05:30 AM

P: 688

The totient function gives you an upper bound for f(x), but it is not necessarily the same as f(x). A counterexample occurs with x=12.
The coprimes to x are 1, 5, 7 and 11. An exponent of 1 won't work, but 2 will: 1^2 == 1 (mod 12) 5^2 = 25 == 1 (mod 12) 7^2 = 49 == 1 (mod 12) 11^2 = 121 == 1 (mod 12) so f(12)=2, while phi(12)=4. (I I understood the problem correctly, f(x) would be the order of the multiplicative group modulo x. As such, f(x) divides phi(x), but it's not necessarily equal.) (By the way, f(3)=2 and f(4)=2, but f(12)=2 and not 4, so f(x) cannot be multiplicative.) 


Register to reply 
Related Discussions  
Calculation of Large Exponents Modulo a Prime  Calculus & Beyond Homework  2  
Order of 3 modulo a Mersenne prime  Linear & Abstract Algebra  4  
Modulo a prime  Calculus & Beyond Homework  1  
Binomial coefficient modulo a prime  Linear & Abstract Algebra  1 