Equal Modulusly?

Algebra Level 3

True or False?

For positive integers x , y , x, y, and n , n, x × ( y m o d n ) = y × ( x m o d n ) . x \times ( y \bmod n) = y \times ( x \bmod n ).

Note: The notation ( a m o d n ) (a \bmod n ) refers to the remainder when a a is divided by n n . It is between 0 and n 1 n -1 inclusive.


Bonus:

  • What if we extend to real numbers x , y , x, y, and n n ?
  • What does this imply about complex exponentiation?
True False

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Calvin Lin Staff
Jan 2, 2017

(For now, let's work in positive integers)

Even though the statement seems true, esp for small numbers, it is actually false. As a counter example, take x = 1 , y = 2 , n = 2 x = 1, y = 2, n = 2 . We have

x × ( y m o d n ) = 1 × 0 = 0 , y × ( x m o d n ) = 2 × 1 = 2. x \times ( y \mod n) = 1 \times 0 = 0, \\ y \times ( x \mod n ) = 2 \times 1 = 2.


The true statement is

( x × ( y m o d n ) m o d n ) = ( y × ( x m o d n ) m o d n ) \left( x \times ( y \mod n) \mod n \right) = \left( y \times ( x \mod n ) \mod n \right)

where both values are equal to ( x y m o d n ) (xy \mod n ) . (Can you show this?) When we tried small values, most things happen to cancel out. However, in general, without taking the final mod n, we could have different values of the residue class.

Note: The original statement is true if x , y < n x , y < n , which is why "small cases work". To get a counter example, we will need one or x n , y n x \geq n, y \geq n .


(Now, let's extend it to real numbers.)

The "true" statement is no longer true when applied to the reals. As a counter example, take x = 1.1 , y = 3.1 , n = 1 x = 1.1, y = 3.1, n = 1 . Then,

( x × ( y m o d n ) m o d n ) = ( 1.1 × . 1 m o d 1 ) = 0.11 , ( y × ( x m o d n ) m o d n ) = ( 3.1 × . 1 m o d 1 ) = 0.31 , ( x y m o d n ) = ( 3.41 m o d 1 ) = 0.41 \left( x \times ( y \mod n) \mod n \right) = \left( 1.1 \times .1 \mod 1 \right) = 0.11 , \\ \left( y \times ( x \mod n ) \mod n \right) = \left( 3.1 \times .1 \mod 1 \right ) = 0.31 , \\ \left( xy \mod n \right) = \left( 3.41 \mod 1 \right) = 0.41

Note: The original statement is true if x , y < n x , y < n . Again, to get a counter-example, we will need one or x n , y n x \geq n, y \geq n .


Now, let's apply what we've learnt to complex exponentiation with evaluation at the principle branch of the argument: [ 0 , 2 π ] [ 0, 2 \pi ] .
When we want to say that

( e x ) y = e x y = ( e y ) x , \left ( e ^ x \right) ^ y = e^{xy} = \left( e^y \right) ^ x,

what we actually mean is

( y × ( x m o d 2 π ) m o d 2 π ) = ( x y m o d 2 π ) = ( x × ( y m o d 2 π ) m o d 2 π ) \left( y \times ( x \mod 2 \pi ) \mod 2 \pi \right) = \left ( xy \mod 2 \pi \right) = \left( x \times ( y \mod 2 \pi ) \mod 2 \pi \right)

However, because this statement is not always true, hence complex exponentiation with evaluation is not always true.


In particular, is it true that

lim x 0 ( e x ) 1 x = 1 ? \lim_{ x \rightarrow 0 } \left ( e^ x \right) ^ { \frac{1}{x} } = 1 ? lim x 0 ( e 1 x ) x = 1 ? \lim_{ x \rightarrow 0 } \left ( e^ \frac{1}{x} \right) ^ { x} = 1 ?

Hint: Try various subsequences like x n = 1 n , 1 2 n π , 2 π n , x_n = \frac{1}{n}, \frac{ 1 } { 2n \pi }, \frac{ 2 \pi } { n}, \ldots

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...