Proving gcd(a,n)=(a-1,n)=1 and its implications on mod calculations

  • Context: Graduate 
  • Thread starter Thread starter 1+1=1
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around proving certain properties related to the greatest common divisor (gcd) and modular arithmetic, specifically focusing on the implications of the conditions gcd(a,n)=(a-1,n)=1. Participants explore various proofs and mathematical concepts, including Fermat's Little Theorem and the behavior of congruences.

Discussion Character

  • Debate/contested
  • Technical explanation
  • Homework-related

Main Points Raised

  • One participant expresses difficulty in completing proofs and seeks guidance on showing that if gcd(a,n)=(a-1,n)=1, then 1+a+...+a^0 mod n.
  • Another participant questions the clarity of the original post, particularly regarding the truth value of the expression "1 + a + ... + a^0 mod n," suggesting that a^0 should equal 1.
  • Concerns are raised about the notation used, with one participant asking for clarification on the meaning of "m 1 mod (mn)" and the term "(^k)."
  • Some participants emphasize the importance of clearly phrasing mathematical questions to facilitate understanding and assistance.
  • One participant expresses frustration with the perceived lack of effort in attempting the problems before seeking help, suggesting that students should engage more deeply with the material.
  • Another participant defends the relevance of number theory and congruences, arguing that these concepts have practical applications, despite the original poster's view that they are not useful for teaching high school mathematics.

Areas of Agreement / Disagreement

There is no consensus on the clarity of the original questions or the relevance of number theory in teaching. Participants express differing views on the necessity of understanding these concepts and the effort required to engage with them.

Contextual Notes

Participants highlight limitations in the original post's clarity, which may hinder effective communication and assistance. There are unresolved questions regarding the notation and the implications of the proposed proofs.

1+1=1
Messages
93
Reaction score
0
i just can't finish up these proofs but i have my ideas written down on the bottom. also, i have what i think is right written down, but it IS A LOT of stuff to type. can anyone point me in the correct direction to go?

i need to show that if gcd(a,n)=(a-1,n)=1, then 1+a+...+a^0 mod n

show (m,n)=1 then m 1 mod (mn)

show if m and k are positive integers then (^k)=m^k-1(m)

what i know so far: the second one can use fermat's little theroem correct? if a==0 mod b and b==0 mod a then => ab==0 mod(ab)

the third one is just playing with my brain, i honestly do not know anywhere to start it.

the first question says what a,n are relatively prime, and a-1,n are also relatively prime. so, if any a raised to a power, that a is == to 0, mod n. can anyone give me a "hint"?

thank you! p.s. does my LaTeX look good? feel free to tell me and all. :redface: :smile:
 
Physics news on Phys.org
1+1=1 said:
i just can't finish up these proofs but i have my ideas written down on the bottom. also, i have what i think is right written down, but it IS A LOT of stuff to type. can anyone point me in the correct direction to go?

i need to show that if gcd(a,n)=(a-1,n)=1, then 1+a+...+a^0 mod n
What? Your consequent is "1 + a + ... + a^0 mod n." I don't see how that can even be assigned a truth value. Wouldn't a^0 just be 1 (assuming we're talking about natural numbers for a).

show (m,n)=1 then m 1 mod (mn)
Again, the consequent is "m 1 mod (mn)." Is this supposed to make sense. Perhaps it's some notation I've never seen, as I've really dealt much at all with number theory.

show if m and k are positive integers then (^k)=m^k-1(m)
What is (^k)? And isn't 1(m) simply m?

thank you! p.s. does my LaTeX look good? feel free to tell me and all. :redface: :smile:
You didn't use any LaTeX (although you probably should have)!
 
1+1=1,

I strongly suggest you re-write your questions more carefully. It's too much effort for us to have to decipher what you mean. Try to spend some time phrasing your queries in a manner that would be easy for others to comprehend. It's not fair that we have to spend a whole bunch of time guessing your intent.
 
At the risk of sounding pissy again, when you say: I can use Fermat's little theorem, right, (paraphrasing) it demonstrates you've not actually attempted the question. This does not make you stuck, seeing as you've not started it. You don't just read a maths question and see the answer anymore, you have to do some work and think it through. When you become a maths teacher, how would you respond to a kid who when asked why they couldn't do a question said something like 'cos I've not tried to do it'?
 
as i say to everyone, i intend to teach useful mathematics, not abstract. my intentions are to teach algebra, geometry, trig., etc. the usefulness of this number theory to me is tasteless in my classroom and i am only in this class because of requirements. do you honestly think that students in the high schools actually understand congruences and modulos? i know of some that cannot even understand basic mathematical concepts, i.e. addiing, subtracting, multi, and division.

again, i wonder to myself i know that i may not be the best descriptive person on my math problems, but still that does not mean i get a verbal bashing everytime i make a type-o. look at others' posts, critique them too. i only ask for a little help, and i get haggled...
 
Last edited:
oh, cos no one's ever found a use for number theory and congruences, right...

but that still doesn't affect the idea that you might meet some students who have exactly the same attitude towards what you consider useful mathematics, and they don't?

sorry it's to your distaste to have to learn the subject that enables you to, say, buy books from amazon online and not have your credit card ripped off, but irrespective of what the subject is you don't appear to be even trying to understand how to do the questions, and if you can't be bothered to learn it (and these questions are both simple and elegant) why should we be bothered to explain it?
 

Similar threads

Undergrad Understanding the Results of gcd(x,n)
  • · Replies 8 ·
Replies
8
Views
2K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
  • · Replies 3 ·
Replies
3
Views
3K
Graduate When n*(n+1)/2 - k is never a square
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Coefficients of Chebyshev polynomials
  • · Replies 2 ·
Replies
2
Views
3K
Prove ## a/d\equiv b/d \mod n/d ##.
  • · Replies 2 ·
Replies
2
Views
1K
Graduate Modular forms, dimension and basis confusion, weight mod 1
  • · Replies 12 ·
Replies
12
Views
2K
MHB Is $ \mathbb{Z}_p $ an Integral Domain and Principal Ideal Domain?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Proving inequality about dimension of quotient vector spaces
  • · Replies 25 ·
Replies
25
Views
5K
Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
2K
Undergrad Prove Even # Transpositions in Identity Permutation w/ Induction & Contradiction
  • · Replies 8 ·
Replies
8
Views
5K