Prove if x^2 is divisible by a prime p then so is x

I am trying to use the contrapositive by proving if x is NOT divisible by p then neither is x^2.

But I don't know how to it for a general prime p?

Reply 1

Gregorius

Original post by lightningdoritos

I am trying to use the contrapositive by proving if x is NOT divisible by p then neither is x^2.

But I don't know how to it for a general prime p?

The answer to a question like this depends critically upon where you are starting and what you can assume. For example, If you allow the fundamental theorem of arithmetic, break x down into its prime components and the proof is trivial; slightly less far along the line, if you assume Euclid's lemma, the proof similarly follows immediately. So, what are you allowing as your starting point?

(edited 8 years ago)

Reply 2

Zacken

Think of the powers of the primes in the prime factorisation of x^2.

Reply 3

username1226161

I'd like to try both but I'm more used to using euclids lemma

Reply 4

Gregorius

Original post by lightningdoritos

I'd like to try both but I'm more used to using euclids lemma

So the proof follows immediately from Euclid's lemma. However, if you want to prove it in the way you suggest, then use Euclid's lemma to prove the FTofA and then proceed as Zacken has suggested.

Reply 5

math42

You can also use strong induction to prove the fundamental theorem of arithmetic. If you wanna be really safe, first use the Well Ordering Principle to prove the Principle of Induction. :tongue:

Original post by lightningdoritos

I'd like to try both but I'm more used to using euclids lemma

Reply 6

Zacken

Original post by 1 8 13 20 42

You can also use strong induction to prove the fundamental theorem of arithmetic. If you wanna be really safe, first use the Well Ordering Principle to prove the Principle of Induction. :tongue:

Relax, m9. :rofl:

Have you been revising too much number theory? :wink:

Reply 7

math42

Original post by Zacken

Relax, m9. :rofl:

Have you been revising too much number theory? :wink:

I mean OP must want to prove it using more than just ftoa or else it's trivial no.. :colondollar:

I have indeed, which isn't good because I should be studying the much trickier sets and countability stuff lol

Reply 8

Zacken

Original post by 1 8 13 20 42

I have indeed, which isn't good because I should be studying the much trickier sets and countability stuff lol

Ooh, those are much more fun than number theory, although, to be fair - I've only done the really basic stuff, cardinal numbers, bijections between this set and that, aleph-naught, etc...

What twisted things are in the course? :biggrin:

Reply 9

Louisb19

Didn't we have a question very similar to this a few weeks ago?

I believe the solution related to prime factors.

Reply 10

math42

Original post by Zacken

The stuff is mostly that basic but the past paper questions are not lol, probably because I missed lectures and the notes leave the actually difficult stuff as exercises without solutions. :colonhash:

It ties it into the function theory a lot, using injections and inverses and all that in the proofs; there's also power sets, a little bit on transcendental vs algebraic numbers, unions of countable sets; there's the Schroeder-Bernstein Theorem, which I hope they do not ask us to name, and its convoluted proof.
edit: well the proof given is more long and unsatisfying than convoluted

(edited 8 years ago)

Reply 11

Zacken

Original post by 1 8 13 20 42

This is first term Warwick stuff? Impressive. :-)

How many lectures do you miss? :rofl:

Reply 12

math42

Original post by Zacken

This is first term Warwick stuff? Impressive. :-)

How many lectures do you miss? :rofl:

Yeah but there are also questions on finding nth roots of unity and ones on showing that a number is a root of a polynomial by substitution so it balances out. :tongue:

To be fair I was very consistent, apart from the super boring physics module I ended up dropping, until maybe the last week when I missed practically everything. Oh and a fair few differential equations ones before that because I lost the will to live trying to follow those lectures...