Modulo and Prime Numbers: Exploring the Multiplicative Function f(x)

In summary, the function f(x) will give us the smallest integer m such that y^m \equiv 1 \bmod{x} given that x and y are coprime. However, there is a caveat that y is dependent on x just as m is. Additionally, the function is not necessarily multiplicative.
  • #1
Texan
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:
Physics news on Phys.org
  • #2
How does y come in? Is it another given? If so, isn't it f(x, y)?
 
  • #3
haruspex said:
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
ramsey2879 said:
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
phillip1882 said:
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
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:

What is a modulo?

A modulo, denoted by the symbol %, is a mathematical operation that calculates the remainder after division of one number by another.

What are prime numbers?

Prime numbers are positive integers that are only divisible by 1 and itself. They have no other factors. Examples of prime numbers include 2, 3, 5, 7, 11, and so on.

What is the significance of prime numbers in cryptography?

Prime numbers are used in cryptography to generate public and private keys. The security of these keys relies on the difficulty of factoring large prime numbers.

What is the difference between modulo and remainder?

The modulo operation calculates the remainder after division, while the remainder is the leftover value after division. For example, 9 % 4 = 1, but the remainder of 9 divided by 4 is 1.

How are prime numbers used in computer science?

Prime numbers are used in various computer science applications such as hashing, generating random numbers, and error-correcting codes. They are also used in algorithms for efficient searching and sorting.

Similar threads

Replies
1
Views
705
  • Linear and Abstract Algebra
Replies
17
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
990
  • Calculus and Beyond Homework Help
Replies
4
Views
928
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
4
Views
3K
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
Back
Top