Modular Arithmetic, and systematic approach.

In summary, the conversation discusses congruences and modular arithmetic, specifically finding the smallest integer n that satisfies the equation 3^n ≡ 1 (mod 7). It is suggested to use Fermat's little theorem, and the process is explained in detail. The same method is applied to solve the equation 5^n ≡ 1 (mod 17) and it is also suggested to check factors of p-1 in the exponent. The conversation also touches on using modulo arithmetic to simplify calculations and the use of archaic words in the English language.
  • #1
kioria
54
0
Hi,

Can somebody drill me on the "congruences and modular arithmetic"? I know it is a big topic, but I think I am missing "something" in my knowledge... These things seem very unusual to me, and makes no sense sometimes.

Find smallest integer n, where:
[tex]3^n \equiv 1 (mod 7)[/tex]

Is there a systematic way of doing a such thing?
 
Physics news on Phys.org
  • #2
You could always apply Fermat's little theorem (it states that a^(p - 1) = 1 (mod p)), so n = 7 - 1 = 6 will work. But I don't know if it guarantees that this is the smallest such number in the general case (in this case it is, as good old-fashioned brute force reveals...).
 
Last edited:
  • #3
Muzza said:
You could always apply Fermat's little theorem (it states that a^(p - 1) = 1 (mod p)), so n = 7 - 1 = 6 will work. But I don't know if it guarantees that this is the smallest such number (in this case it is, as good old-fashioned brute force reveals...).

There are others such as:
[tex]5^n \equiv 1(mod 17)[/tex] OR [tex]5^n \equiv -1(mod 17)[/tex]
In which case the n = 8.
So:
[tex]5^8 \equiv -1[/tex]
Can somebody explain the above notation as well, thank you.

Very confusing to me right now.
 
Last edited:
  • #4
You can apply Fermat's little theorem on 5^n = 1 (mod 17) too. As for the second problem, I suppose "trying all possible values for n" classifies as systematic ;)
 
  • #5
To solve the ones equal to one, when you are working mod a prime remember that these things are a group. so the order must divide p-1, so it suffices to check the factors of p-1 in the exponent.

so for 3 mod 7, well, p-1=6 here, so you only need to check 1,2,3. Clearly none of these produces 1 mod 7 so the answer must be 6, and therefore 3 generates the units mod 7.

Now 5 mod 17, p-1=16, so you need to check the powers 1,2,4,8 (and again if none of those works then it must be that the order is 16).

Suppose you've found the answer, I don't know what it is by the way, as I'm too lazy to do it in my head. But suppose the order is r, it is even, so what is 5^{r/2}? it must be an element that squares to give 1, and at the same time can't be 1 (as r is minimal) so it must be -1 (there are only two square roots of any number mod a prime at most).
 
  • #6
matt grime said:
To solve the ones equal to one, when you are working mod a prime remember that these things are a group. so the order must divide p-1, so it suffices to check the factors of p-1 in the exponent.

so for 3 mod 7, well, p-1=6 here, so you only need to check 1,2,3. Clearly none of these produces 1 mod 7 so the answer must be 6, and therefore 3 generates the units mod 7.

Now 5 mod 17, p-1=16, so you need to check the powers 1,2,4,8 (and again if none of those works then it must be that the order is 16).

Thank you, so I will only need to check integers that are factors of p-1. Is that right? And, if it is right, in a test where calculators are not allowed, how would one check [tex]5^{16}[/tex]! Total Insanity!

matt grime said:
Suppose you've found the answer, I don't know what it is by the way, as I'm too lazy to do it in my head. But suppose the order is r, it is even, so what is 5^{r/2}? it must be an element that squares to give 1, and at the same time can't be 1 (as r is minimal) so it must be -1 (there are only two square roots of any number mod a prime at most).

I didn't get this part, r = 8, and the explanations following r I do not understand. Am I seriously missing something here?
 
  • #7
one wouldn't need to check 5^16

here's how to do it sans calculator (playing up to the pommie as much as I can)

5^2 = 25=8mod17

5^4=(5^2)^2 = 8^2=64 = 13 mod 17

5^8=((5^2)^2)^2 = 13^2 = 169 = 16=-1 mod 17

all done in my head, not even using paper.

as none of those is 1 it must be that the order is 16 (x^{p-1} is always 1 mod p a prime this never needs checking)


but in any case 5^16= (((5^2)^2)^2)^2 = (-1)^2 = 1 mod 17

in the process of this you see that 5^8=-1 and is the smallest power with this property. note that this is the order 5, 16, divided by two. that is not a coincidence. If you want to see why reread my post and think about it for a while.
 
  • #8
thinking...

haha never knew what sans actually meant, looked it up on the dictionary, and it actually states: Rarely used as an English word. Wonder how else it is used.
 
  • #9
shakespeare, seven ages of man speech: sans teeth sans eyes.
wonder if the French are happy with us using their words, they don't like english ones in french after all. Oh, and today's cricket is rain affected.

which bit you thinking about? that when doing modulo arithmetic you dont; have to do all the arithmetic first then the modulo bit? useful observation.

suppose I wanted to work out (2^5)*(3^6)*(6^5)*(9^6) mod 17 well, I can note that 2*9=18=1 mod 17, and 3*6=1mod 18,, so that collecting and cancelling I end up with 3*9 = 27=10mod17
 
Last edited:
  • #10
matt grime said:
shakespeare, seven ages of man speech: sans teeth sans eyes.
I was never a strong contender for English during my high school years. So I guess sans is one of those archaic words, like thee, thy and thou. A new word in my vocab...

matt grime said:
wonder if the French are happy with us using their words, they don't like english ones in french after all. Oh, and today's cricket is rain affected.
Only if I had time to watch my sports news, I have two tests tomorrow, and I can't afford to lose a mark. Aiming for HD average this semester... the first semester :D. I have to say, maths, I generally find it hard to understand its concepts but interesting enough to get me going forever just to understand one thing. By the way, you seem to be overloaded with maths knowledge, can I ask you what you do?

matt grime said:
which bit you thinking about? that when doing modulo arithmetic you dont; have to do all the arithmetic first then the modulo bit? useful observation.

suppose I wanted to work out (2^5)*(3^6)*(6^5)*(9^6) mod 17 well, I can note that 2*9=18=1 mod 17, and 3*6=1mod 18,, so that collecting and cancelling I end up with 3*9 = 27=10mod17
Yes, modular arithmetic certainly is easier when carried out like you showed me. And interestingly, the part b) of the question I asked above was something like, Evaluate [tex]5^{243} (mod 17) \equiv 6[/tex]. And I did it! Thank you!

I still think I am mis-understanding some portions of Modular Arithmetic. But having this in my mind, I guess rest is upto my research (mind you this was the last part in the M.Arithmetic syllabus).
 
Last edited:
  • #11
I can't resist an opp to quote Shakespeare, so forgive me that it's not math related.
By my quick count, Shakespeare used the word "sans" 16 times, but I think its meaning is best exemplified by the line "My love to thee is sound, sans crack or flaw."
How could the French mind that? :)
Happy thoughts
Rachel
BTW I have just started reading Arthur Clarkes's translation of Gauss' Disquisitiones Arithmeticae, and, so far, it is the best explanation of modular arithmetic I've read. Maybe it would clear things up for you. Read the masters, right? :)
 
Last edited:
  • #12
So have I. I wish he would leave a blank line between results - would make it a lot easier on the eye.
 

What is modular arithmetic?

Modular arithmetic is a type of mathematical operation that involves working with remainders. It is often used when dealing with cyclic patterns or repeating phenomena. In modular arithmetic, numbers are divided by a fixed number called the modulus, and the remainder is taken as the result.

What is the systematic approach to solving problems involving modular arithmetic?

The systematic approach to solving problems involving modular arithmetic involves breaking down the problem into smaller, more manageable parts, and applying the rules of modular arithmetic to each part. This helps to simplify complex calculations and make it easier to find patterns and solutions.

What are the key concepts in modular arithmetic?

The key concepts in modular arithmetic include the modulus, which is the fixed number used for division, and the remainder, which is the result of the division. Other important concepts include congruence, which means two numbers have the same remainder when divided by the same modulus, and the multiplicative inverse, which is a number that, when multiplied by the original number, gives a remainder of 1 when divided by the modulus.

How is modular arithmetic used in real life?

Modular arithmetic has many applications in real life, including in computer science, cryptography, and music theory. It can be used to encrypt and decrypt messages, generate random numbers, and create musical scales and chords. It is also used in the calculation of time, such as determining what day of the week a particular date falls on.

What are the benefits of using modular arithmetic?

Using modular arithmetic can make complex calculations easier and more efficient. It also allows for the identification of patterns and relationships between numbers. This can be useful in problem-solving and finding solutions to real-world problems. Additionally, modular arithmetic has practical applications in various fields, making it a valuable tool for scientists, engineers, and mathematicians.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
Replies
5
Views
2K
Replies
1
Views
1K
Replies
1
Views
2K
  • General Math
Replies
4
Views
2K
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
12
Views
2K
Replies
4
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
3K
Back
Top