Am I just not smart enough? When I was doing math, let us say for example, introductory number theory, it seems to take me a lot of time to fully understand a theorem. By understanding, I mean, both intuitively and also rigorously (know how to prove or derive). However, I really find many results (even elementary results like euclidean algorithm or things like $ax+by=\gcd(a,b)$) hard to intuitively understand. I usually will be thinking about these theorems most of the spare time, whenever I am not doing anything requires my thought... 
Even if I do comprehend, it takes a long time until I fully comprehend the theorem. And sometimes I may even forgot them(maybe I didn't actually fully comprehend) I feel like I am spending tons of time more than others on number theory. I mean, many of people online claim that introductory number theory is easy. Is that I am not smart enough to do mathematics and make contribution to the world of math later on since great mathematicians must have great intuition, or is that other people are not fully comprehending the theorems and it really does take a lot of time to just figure out one theorem completely?
I am very confused. I like math, but I really want to know if I am capable of doing it and make contributions. And I wish to make the best choice for myself. I appreciate any good comments or advices!
 A: Let me give you a personal story. As a young kid, I was always very strong in math but was pretty hampered by one of the worst educational environments in the USA. I ended up entering a magnet school for junior high and had to take a math placement exam to determine which of three math classes I would join: regular math, pre-algebra and algebra. I didn't do quite well enough to fully justify being placed in algebra but did a bit too well to justify holding me back in pre-algebra. So as a seventh grader, I was placed in algebra. I struggled with it immensely. I had a private tutor and studied tons but to no avail. Ended up getting a 36 average or so and dropped down to pre-algebra in which I got a 105 average. Eighth grade came around and I had to take algebra; again, I didn't do that great but was better than before. I ended up with a low 70.
I did very well in geometry in high school but again not so great in algebra 2. Pre-calculus was hit-and-miss: some topics I did very well in, some not so well in. It was not until calculus that I really began to understand math at an intuitive and deep level.
Since taking calculus, I've excelled in mathematics. I ended up with nearly a 4.0 GPA in my math courses in undergrad (one A-) and I am currently in graduate school doing pure math after all of the struggle I went through. I'm pursuing very difficult and unique research and am very fluent in various aspects of mathematics. Just because you are struggling now does not mean you are incapable. Plenty of good mathematicians had trouble with math at some point for one reason or another. Don't throw in the towel so soon if you really like the material!
A: In my mind, "understanding intuitively" means that you understand something in terms of things you know really well from your past experiences. This means that you need to gather experiences to have a lot of intuition. That is, mathematical experiences to build mathematical intuition, and mathematical intuition to understand mathematics. Other kinds of experiences, such as knowing how physical objects behave, would help a lot but doing mathematics that really counts. Especially, there are a lot of structures in mathematics that do not even remind you of things you would experience in the real world. When you teach higher mathematics to relatively inexperienced audience, there is always a risk in trying to make everything "intuitive", because this can oversimplify or completely distort the real picture. In any case, what you are doing is good. Question everything, and move forward slowly but surely. One day, you will notice that a lot of things you thought were unintuitive became trivial matters.
On another note, people learn things differently, and it can happen that the current teacher's approach is basically the opposite of what would be the ideal approach for you. If you suspect if it might be the case, you can study from books independently and see if it helps.
A: Think of mathematics as a language.  Some people are native speakers or have a gift for speech, some have to work at it, some people stutter.
Replace "math" with "French" in your question above.  It will get easier the more you do it, even if you don't become a fluent speaker.
A: I don't think the time it takes to learn a concept is necessarily an indication of ones intelligence. Some people are quick learners and some aren't. Of course there are advantages to learning quickly; however, perhaps when you do finally understand a concept, you understand it better than those quick learners! 
With this in mind, some people just aren't so strong mathematically. It's hard to say based on what you wrote if that applies to you, but I don't think so. Introductory concepts are often hard to learn at first. I think many people currently studying mathematics can sympathize with it taking a long time to understand a concept, or to forget something you recently learned.
I think if one isn't strong enough mathematically it wouldn't be something that they would be truly passionate about.
You should do math if it is something that excites you and something you get enjoyment out of. If it is your passion then you will be willing to put in the work it requires to understand concepts and make contributions. 
A: If you are smart enough to be in number theory, then you are smart enough to understand it. If you are smart enough to choose number theory as your field of study, then you are smart enough to find your way to your goal. I am not just saying that.
Considering the amount of time you have been spending studying number theory, your brain has been taking in much information and will process it subconsciously. Some time when you are not even thinking about mathematics or anything related to it, number theory related thoughts might come to mind. Years from now, you will understand things which presently you might think you cannot understand.
A: The late great Paul Sally told me a story about his days as a post-doc.  He was struggling with his research, and complained to his mentor, "I'm busting my a** and I still can't get a theorem!"  
The mentor replied that yes, hard work is necessary for good results.  In consolation, he replied that "In time, you'll find it's sufficient."
Apologies for the name drop.  It's necessary to read the quote in his native Bostonian inflection.
A: When you say that you're experiencing some difficulties understanding intuitively some elementary things, there are a couple of possibilities: 
1 - By "understanding intuitively", you actually mean the point in which you have devoted enough time and effort to certain topic that everything becomes clear and straightforward. That is what understanding something really means. Most people don't reach this stage as they stop their learning process when something "makes sense".
2 - If you regard "intuition" as an immediate understanding in the same way we know that 1+1=2, let me tell you that most mathematical concepts are not amenable to that kind of intuition. As timur said, many concepts in mathematics don't have parallel in the real world. Therefore, you can not expect the euclidean algorithm and 1+1=2 to produce the same "result" in your brain. As Von Neumann said:

Young man, in mathematics you don't understand things. You just get
  used to them.

That's what happens. You get used to dealing with very elaborate concepts and they become second nature to you.
Finally, if you forget something you spent a great deal of time studying it but after refreshing your knowledge, you are able to regain that understanding quickly and somewhat effortlessly, it means you actually understood it very well the first time. That's how the human brain works when it comes to nonessential things.
A: When I learned number theory, I found that I had no intuition for anything about the proofs, where my classmates seemed to pull the things from thin air; in math, there's always that little (or not-so-little) brilliant leap required for the proof. When I just started learning number theory, I had no idea how people were figuring these things out - even knowing the proofs, I found them hard to follow. I don't really think I got up to speed with my intuition until months after initially seeing the material.
This would be because I was learning math and could, naturally, not do it very well. Nowadays, I see such proofs as entirely trivial and have no idea what was so hard for my past self to see in this. There's something intangible at work here and when you're just starting it can be easy to see these objective things - like other people being so much quicker to the proof than you - and to not know what you're missing, but, with practice in mathematics, it may come. If you like math, there's no reason to stop now.
A: Something to understand is that although it may all look the same from the outside, each branch of mathematics is quite different. They all have a different feeling, different ways of approaching problems, different levels of rigor. My personal story is that I've always been one of those people who just "gets" math. I'd be able to look at problems and either guess the answer or the right approach to the answer. I'd anticipate new ideas before the professor introduced them. Basically mathematics "fits" my brain.  
And then I took a course in differential geometry, and it just didn't work. I couldn't "get" it. I understood the concepts from a definitional point of view, the same way a computer would if you taught it the axioms, but I had no intuition about how tensors work, what forms, bundles, etc. are, or how to approach even simple problems. The professor was excellent; I had great experiences with him from other courses. My conclusion was that unlike most (really all) other mathematics that I had encountered up to that point, differential geometry really did not fit my brain. It was a bit of a shock, but an important lesson. 
So what I'd say to you is if you can't get number theory, don't worry about it. It might not be the math for you. There are lots of mathematicians who are terrible at number theory (there's a famous story about Grothendieck, the father of modern algebraic geometry, who thought that 57 was prime). Try other fields of mathematics. Maybe analysis is your cup of tea. Or maybe it's algebra. Or topology. Or logic. Or combinatorics. Or probability and statistics. Each has such a different feel to it that most mathematicians will hate or at least strongly dislike working in at least one subfield, if not most subfields other than their own. 
It is good to know the basic concepts from each subfield of mathematics, just so that you are aware of what's out there. It can give you new insight to ways to solve problems, and perhaps most importantly it can show you what kinds of problems have already been solved in case you encounter them doing something else. 
A: It is often a matter of technique. Once you master the technique you advance easy and fast, but before that it is many long stops. Those who dwells in this first state may also achieve more insight into the next stage? And previous knowledge really means a lot (that's why it take such a long time breaking new grounds).
A: Listen! You don't need to ask others for whether you want to continue in math or have potential. Based on what you said, which is thinking about Math in all your spare time, I'd say you could be a genius already, just not fully developed! Take you time and enjoy the process. Many people seem to think they are good at math, but all they are doing is memorizing formulas and becoming human calculators! 
Don't depend on other's opinions for such matters, this is about you! Only you can answer if whether or not you can do it. Don't feel pressured to contribute to math either. That is a very hard thing to do in this day an age where is's already so developed. Ancient Greeks had (IMHO) a much easier time coming up with new math concepts then we do today since it was much more foundation and basic then.
I'd hate to see someone with so much interest in math, give up because they don't think they are as good as others. I'm telling you don't give up unless you really don't enjoy it, but if you do, don't! The education system rewards those who are the human calculators the most IMO, but that shouldn't stop you from going beyond it and excelling to your dreams.
Personally, I was the type who hated the human calculator system, but didn't enjoy math enough to think about it as much as you. I thought I was stupid, but really I actually wanted to "understand" math at a deep level, and it just wasn't taught in my school. All I learned was formulas and little tricks such as FOIL and the like.
You will have to learn that you are your greatest teacher, and that you are the only one that can really speak "your" language. Teach yourself with "your" language. 
I wish someone told me this when I was in your shoes. :) Good luck and just remember to enjoy the process. The most successful people aren't the most organized or talented, but those who love what they do the most because they are operating in their optimal mindset.
Also, I don't believe there are those that are good at Math and those that aren't!
Some have had better teachers than others, some had their parents help them with homework when they were young. Everyone had a different experience learning math, and some had more help, and more advantages. But that shouldn't stop you, in fact, the ones without all the advantages tend to succeed more. Just study the richest businessmen, they often came from poor backgrounds.
