Modulo and prime numbers

  • Thread starter Texan
  • Start date
  • #1
3
0
[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 (p-1). 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.
 
Last edited:

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,837
6,113
How does y come in? Is it another given? If so, isn't it f(x, y)?
 
  • #3
841
0
How does y come in? Is it another given? If so, isn't it f(x, y)?
I don't think so because y is dependent on x just as m is. I.E. y is any number coprime with x.
 
Last edited:
  • #4
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,837
6,113
I don't think so because y is dependent on x just as m is. I.E. y is any number coprime with x.
Rereading it, I think we're both wrong. It should say "for all y coprime to x". (Otherwise the later part about f(p) = p-1 is wrong.) In short, this f(x) is Euler's totient function.
 
  • #5
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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,837
6,113
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.
As I said, I think the question is intended as "for all y". I.e. what is the smallest m that s.t. for every y prime to x the equation is true.
 
  • #7
695
2
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.)
 
Last edited:

Related Threads on Modulo and prime numbers

  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
1
Views
7K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
2K
  • Last Post
2
Replies
28
Views
7K
  • Last Post
Replies
24
Views
6K
  • Last Post
2
Replies
44
Views
11K
Top