Modular Arithmetic (someone check my work please)

In summary, the conversation discusses the proof that for every x in Z and for every natural number n, if x^2 is congruent to 1 mod 47, then x^n is either congruent to 1 or 46 mod 47. This is proven using Fermat's Little Theorem and the fact that 47 is a prime number. It is also mentioned that there may be some steps missing in the argument and that considering (x^2 - 1) may be helpful in proving the statement.
  • #1
mtayab1994
584
0

Homework Statement



For every x in Z and for every natural number n if:

[tex]x^{2}\equiv1(mod47)\Rightarrow x^{n}\equiv1(mod47)orx^{n}\equiv46(mod47)[/tex]



The Attempt at a Solution



Alright I said since 47 is prime and relatively prime with x then by fermat's little theorem we will get:

[tex]x^{46}\equiv1(mod47)[/tex]

and [tex](x^{2})^{23}\equiv1^{23}(mod47)[/tex] so that's case one.

And when multiplying both sides by 46 we will get:
[tex]46(x^{2})^{23}\equiv46*1^{23}(mod47)[/tex]

which is [tex]x^{47}\equiv46(mod47)[/tex].

So then i was able to conclude that if n=2k such that k is an integer we get:
[tex]x^{n}\equiv1(mod47)[/tex]

And if we have n=2k+1 (odd number) such that k is an integer we get:

[tex]x^{n}\equiv46(mod47)[/tex]

Is that correct?
 
Physics news on Phys.org
  • #2
It seems like there are a lot of steps missing in this argument.

Choosing n=1, it is clear that no more is needed than to show that ##x \equiv 1 \text{ mod } 47## or ##x \equiv 46 \text{ mod } 47##.

Consider ##(x^2-1)##...
 
  • #3
Joffan said:
It seems like there are a lot of steps missing in this argument.

Choosing n=1, it is clear that no more is needed than to show that ##x \equiv 1 \text{ mod } 47## or ##x \equiv 46 \text{ mod } 47##.

Consider ##(x^2-1)##...


Yea and x^-1=(x+1)(x-1)
 
  • #4
... and we know that ##(x^2-1) \equiv 0 \text{ mod } 47## ...
 

1. What is modular arithmetic?

Modular arithmetic is a branch of mathematics that deals with the operations and properties of numbers under a specific type of division called modulus. In this type of arithmetic, numbers wrap around when they reach a certain value, rather than continuing to increase or decrease indefinitely.

2. How is modular arithmetic different from regular arithmetic?

Regular arithmetic, also known as modular arithmetic, operates under the rules of modular arithmetic, while regular arithmetic operates under the rules of regular division. In regular arithmetic, numbers continue to increase or decrease without limit, while in modular arithmetic, numbers wrap around when they reach a certain value.

3. What are some applications of modular arithmetic?

Modular arithmetic has various applications in fields such as computer science, cryptography, and coding theory. It is used in computer algorithms, encryption methods, and error-correcting codes, among others.

4. How do I perform basic operations in modular arithmetic?

In modular arithmetic, the basic operations are addition, subtraction, multiplication, and division. To perform these operations, you first need to choose a modulus, which is the number that determines when numbers "wrap around." Then, you can perform the operations as you would in regular arithmetic, but with the added step of reducing the result to the range of the chosen modulus.

5. What is the significance of modular arithmetic in number theory?

Modular arithmetic is an essential tool in number theory, as it allows for the exploration of patterns and relationships between numbers. It is used to solve problems related to prime numbers, congruences, and other important concepts in number theory.

Similar threads

  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
11
Views
195
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
836
  • Calculus and Beyond Homework Help
Replies
19
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Replies
1
Views
519
Back
Top