Finding the Least Residue of 3^215 (mod 65537)

  • MHB
  • Thread starter toni07
  • Start date
  • Tags
    Residue
In summary, the conversation discusses the computation of the least residue of 3^215 (mod 65537), where 65537 is a Fermat's prime. The conversation also mentions the use of Euler's theorem, Fermat's little theorem, and Wilson's theorem, but none of them seem to work. The conversation also clarifies that 65537 is a Fermat's prime and discusses the application of this fact in solving the problem. Finally, it is revealed that the correct expression should be 3^2^15 instead of 3^215.
  • #1
toni07
25
0
Compute the least residue of 3^215 (mod 65537) (65537 is prime).

I've tried to use Euler's theorem, Fermat's little theorem and Wilson's theorem, but nothing seems to work, please help.
 
Mathematics news on Phys.org
  • #2
crypt50 said:
Compute the least residue of 3^215 (mod 65537) (65537 is prime).

I've tried to use Euler's theorem, Fermat's little theorem and Wilson's theorem, but nothing seems to work, please help.

The number 65537 is not a 'whatever prime', it is a Fermat's prime because is in the form $\displaystyle F_{n}= 2^{2^{n}}+1$. For a Fermat's prime the following holds...

$\displaystyle 3^{\frac{F_{n}-1}{2}} = -1\ \text{mod}\ F_{n}\ (1)$

For n=4 the (1) becomes...

$\displaystyle 3^{2^{15}} = -1\ \text{mod}\ 65537\ (2)$

In your post is written $\displaystyle 3^{215}$ and not $\displaystyle 3^{2^{15}}$... the question is: are You sure to have written correctly?... Kind regards $\chi$ $\sigma$
 
Last edited:
  • #3
Thanks, a lot I didn't realize it was 3^2^15. Thanks for calling my attention to it.
 

FAQ: Finding the Least Residue of 3^215 (mod 65537)

What is the purpose of finding the least residue of 3^215 (mod 65537)?

The purpose of finding the least residue of 3^215 (mod 65537) is to determine the remainder when 3^215 is divided by 65537. This can be useful in cryptography and number theory, as it helps in solving problems related to modular arithmetic.

What is the significance of using 3^215 (mod 65537) in this calculation?

The number 3^215 is a specific value that has been chosen to demonstrate the concept of modular arithmetic. The choice of 3 and 215 is arbitrary and could be replaced with any other numbers. However, using 3^215 allows us to demonstrate the process and reasoning behind finding the least residue.

What is the formula for finding the least residue of a number (a^n) (mod m)?

The formula for finding the least residue of a number (a^n) (mod m) is: a^n ≡ r (mod m), where r is the remainder when a^n is divided by m. This can also be written as a^n = qm + r, where q is the quotient and r is the remainder.

Can the least residue of 3^215 (mod 65537) be negative?

No, the least residue of 3^215 (mod 65537) cannot be negative. This is because modular arithmetic only deals with non-negative integers. If the remainder is negative, we can add m to it until it becomes positive and still get the same least residue.

What are some real-world applications of finding the least residue of a number (a^n) (mod m)?

Finding the least residue of a number (a^n) (mod m) has various applications in cryptography, coding theory, and number theory. For example, in cryptography, it is used to encrypt and decrypt messages, while in coding theory, it helps in error correction. In number theory, it is used to solve problems related to congruences and divisibility.

Similar threads

Replies
1
Views
1K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
1
Views
2K
Replies
5
Views
2K
Replies
2
Views
2K
Back
Top