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

  • Thread starter 1+1=1
  • Start date
In summary, In order to prove that if gcd(a,n)=(a-1,n)=1, then 1+a+...+a^0 mod n, a student would need to know what gcd is, how to calculate it, and understand that if a and n are relatively prime then the result is 1. Additionally, the student would need to know how to show that if m and k are positive integers then (^k)=m^k-1(m). Lastly, the student would need to be able to show that if a==0 mod b and b==0 mod a then => ab==0 mod(ab).
  • #1
1+1=1
93
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
  • #2
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)!
 
  • #3
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.
 
  • #4
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'?
 
  • #5
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 becuase 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:
  • #6
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?
 

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

What is the context of "Please help, almost finished"?

The phrase "Please help, almost finished" is a common plea for assistance when someone is nearing the end of a task or project and needs some extra support or guidance to complete it successfully.

What types of situations might prompt someone to say "Please help, almost finished"?

This phrase can be used in a variety of situations, such as completing a difficult homework assignment, finishing a work project with a tight deadline, or putting the final touches on a presentation or speech.

Why might someone wait until they are almost finished before asking for help?

There are a few reasons why someone might wait until they are almost finished to ask for help. They may have been confident in their abilities to complete the task on their own, they may have underestimated the difficulty or time needed to complete the task, or they may have encountered unexpected challenges along the way.

What are some ways to offer help to someone who says "Please help, almost finished"?

One way to offer help is to ask specifically what they need assistance with. This allows the person to identify the specific areas where they are struggling and the type of help they need. Another way is to offer general support and encouragement, such as offering to proofread their work or providing a listening ear as they talk through their challenges.

Is it important to offer help when someone says "Please help, almost finished"?

It is always a kind gesture to offer help when someone asks for it, but it is ultimately up to the individual to accept or decline the assistance. It is important to respect their decision and not pressure them into accepting help if they do not want it. However, offering support and encouragement can still be beneficial in these situations.

Similar threads

I Understanding the Results of gcd(x,n)
Replies
8
Views
1K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
Replies
3
Views
2K
When n*(n+1)/2 - k is never a square
Replies
2
Views
1K
Prove ## a/d\equiv b/d \mod n/d ##.
Replies
2
Views
926
A Modular forms, dimension and basis confusion, weight mod 1
Replies
12
Views
2K
I Proving inequality about dimension of quotient vector spaces
Replies
0
Views
829
Number of quadratic residues mod N>1
Replies
4
Views
3K
I Prove Even # Transpositions in Identity Permutation w/ Induction & Contradiction
Replies
8
Views
2K
I Fundamental theorem of arithmetic from Jordan-Hölder theorem
Replies
5
Views
463
I Prove that elements of x^i 0<i<n-1 are distinct
Replies
3
Views
1K

Hot Threads

Recent Insights

Back
Top