Question

number theory proof problem regarding Euclid's Division Lemma

Answer 1

Without assuming THeorem 2-1, prove that for each pair of integers j and k(k>0), there exists some integer q for which j-qk is positive

Answer 2

Theorem 2.1 states that
For any integers k (k>0) and j there exist unique integers q and r such that 0 \[\leq\]r < k and j = qk+r

Answer 3

\[0 \leq r< k\]

Answer 4

so suppose I want to provide a proof by contradiction. That would mean that

Answer 5

You know, you don't need to type it out, there's a video already posted online: https://www.youtube.com/watch?v=JhnsHxtP6bk

Answer 6

there aren't any unique integers q and r that are positive

Answer 7

but I want to at least attempt or try before going off and searching on google.

Answer 8

@ganeshie8

Answer 9

you want to try by contradiction is it

Answer 10

if there aren't any unique integers q and r that are positive.... then j=qk+r is negative. or would it be that j-qk would be negative.

Answer 11

yeah proof by contradiction which is basically the negation of th. 2.1

Answer 12

so there aren't any unique integers q and r

Answer 13

are you allowed to use `well ordering principle` ?

Answer 14

let me check

Answer 15

ahhh I see the well ordering principle. It states that
we let \[n_0 \in Z\]
Every nonempty subset \[n \in z: n \geq n_0\] includes a least element

Answer 16

but we don't need to use it here,
this proof is simpler than it appears

Answer 17

how is it simpler? Am I overlooking something?

Answer 18

since we're given that \(\large k \gt 0\),
\(\large|j|k \ge |j|\)

yes ?

Answer 19

I was trying to reread it again.. all I know are the c divides a c divides b stuff. I don't mind if a theorem has examples on how to prove something, but if there is a theorem without an example I am lost.

Answer 20

where did you get the absolute value of j from?

Answer 21

we want to find some `q` that makes `j-qk` positive, right ?

Answer 22

how is this easier to the prove that a^2-b^2 is divisble by 8 if a and b are odd integers. that one is easy.

Answer 23

yeah but by proof through contradcition that would mean that there is a q that makes j-qk negative right?

Answer 24

lol this is easier than everything else that giving hints only makes it complex,
let me give you the full 2-3 lines proof :)

Answer 25

Oh you're not allowed to use direct proof is it

Answer 26

huh? I can either just prove it direct with the theorem or do a proof by contraction or proving the contrapositive.

Answer 27

I think if I go direct ... I can possibly try to get it.

Answer 28

question -> there exists some integer q for which j-qk is positive

th 2.1 ---> there exist unique integers q and r

Answer 29

since \(\large k>0\),
\(\large |j|k >= |j| \)

\(\large j - (-|j|)k = j + |j| k \ge j + |j| \ge 0\)

QED.

Answer 30

so there are more than one typidslajfdk;lafjdfas arghhhhhhhhhhhhhhhhhhhhhhh what just happened?

Answer 31

how did you get that so fast?

Answer 32

I have told u it is easy ;)

Answer 33

step by step please. I had a horrible proof writing professor. Sure I passed the course but lol I only know 5.5 out of 8 chapters

Answer 34

I have no idea how I scored above 6 people XD!

Answer 35

it may be easy to people who have done it before, but not to beginners like me... so show me ^_^! o kudasai

Answer 36

since \(\large k>0\),
\(\large |j|k >= |j| \)

say \(\large q = -|j|\)

Answer 37

\(\large \begin{align}\\ j - qk &= j - (-|j|)k\\~\\&= j + |j|k \end{align}\)

Answer 38

oh

Answer 39

oh could it be from j = qk+ r
and then j-qk??
Suppose we have an integer that's negative. Then we let q = -j?!
so if we let q = -j and then subsitute it in j-qk, we have
j-(-j)k
j+jk?

Answer 40

Yep! all this works because `k` was given as positive to start with

Answer 41

so \(\large |j|k\) is positive too

Answer 42

so did we do a proof directly from the theorem or through contradiction? I'm still slow at this x.x! But at least I try to attempt it... somewhat

Answer 43

we did not use any theorems, and it is not contradiction

Answer 44

what the heck is it ? :O

Answer 45

|j|k >= |j| is a trivial observation

Answer 46

is it because of that k(k>0)?

Answer 47

exactly !

Answer 48

\(\large \begin{align}\\ j - qk &= j - (-|j|)k\\~\\&= j + |j|k \\~\\ &\ge j + |j|~~~~~\color{gray}{(\text{\because k > 0})}\end{align} \)

Answer 49

does that look okay ?

Answer 50

oh so if we let q = -j . Then we subsitute it and abs j becomes positive... and it's positive because k > 0. Then ... the .......ugh thought process overload.

Answer 51

you're right !

q = -|j|

Answer 52

ah because k > 0... all positive numbers only

Answer 53

yep ! ` j ` can be ANYTHING positive/negative

Answer 54

\(\large \begin{align}\\ j - qk &= j - (-|j|)k\\~\\&= j + |j|k \\~\\ &\ge j + |j|~~~~~\color{gray}{(\because \text{k > 0})}\\~\\ &\ge 0\end{align}\)

Answer 55

that ends the proof

Answer 56

can I ask you another question? ^^

Answer 57

sure ask wil try

Answer 58

because I am sort of getting the idea, but not sure how to move forward after I have it

Answer 59

@BSwan / @ikram002p are good with NT proofs like these too

Answer 60

Any set of integers J that fulfills the following two conditions is called an integral ideal:

if n and m are in J, then n+m and n-m are in J
if n is in J and r is an integer, then rn is in J

Let J_m be the set of all integers that are integral multiples of a particular integer m. Prove that J_m is an integral ideal.

Note: there was a script J_m\[J_m\]

I sort of get the idea. Like we have a set of integers in J. So I know that if n and m are in J then n+m and n-m are in J because I assume that n is an integer and so is m.

For if n is in J and r is an integer, then rn is in J.
I understand this as well because we already have n inside the set of integers J.. r is also an integer so it can belong to J as well. So I have a set of all integers, \[J_m\] with integral multiples of a particular integer m. So integral multiples would be that there are certain multiples... like \[2^m\] and I have to prove that \[J_m\] satisfies the two conditions listed above.

Answer 61

I can probably brainstorm this... but afterwards depending on the problem it either becomes doable or a bit challenging for me. That's why I like to work in groups when it comes to these things.

Answer 62

I sort of kind of get the idea... up until " integral multiples of a particular integer m." So there must be certain hmm elements in J.. certain numbers in the set of J (integers)

Answer 63

just to get a quick feel of problem statement :


J_m = {...,-2m, -m, 0, m, 2m, 3m,...}

and we want to prove below two properties :
1) if a and b are in J_m, then a+b and a-b are in J_m
2) if c is in J_m and r is an integer, then rc is in J_m

Answer 64

is that right ?

Answer 65

ya

Answer 66

^_^
i was not sure what does integral multiples of a particular integer m
but i got it nw hehehe

Answer 67

which means those integral multiples need to be in J which is the set of integers. Geez why J? Isn't Z the default letter for the set of all integers?

Answer 68

1)
since \(\large a \in J_m\) and \(\large b \in J_m\),
\(\large a = xm\) and \(\large b = ym\) for some integers \(\large x\) and \(\large y\)

\(\large a+b = xm + ym = m(x+y) \in J_m\)

Answer 69

that ends the proof for first property ^^

Answer 70

similarly see if u can work the second property

Answer 71

WHATTTTTTTTTTTTttttttttttttttttt dang so fast... nani?!

Answer 72

yeah lol these stuff is 10 sec work :P

Answer 73

Ok let me bust open the second one
if n is in J and r is an integer, then rn is in J

So for J_m we have if n is in J_m and r is an integer then rn is in J_m
@Bswan. I am still a beginner at these XD. But, at least I'm trying

Answer 74

1)
since \(\large a \in J_m\) and \(\large b \in J_m\),
\(\large a = xm\) and \(\large b = ym\) for some integers \(\large x\) and \(\large y\)

\(\large a \pm b = xm \pm ym = m(x\pm y) \in J_m\)

Answer 75

ok so my main goal is to get something similar to rn or the exact definition like rn

Answer 76

that will do : n = mx,
rn = r(mx) = m(rx) \(\in J_m\)

Answer 77

we only have one integer n... so we assume that \[b \in J_m\]. Then we have some integer y such that \[b=ym\]. Therefore,
[ym]r

Answer 78

So, [ym]r is in J_m. We have proven the conditions for an integral ideal.

Answer 79

something like that yes !

Answer 80

oops forgot to rearrange XD
[my]r in J_m
he he my r

Answer 81

to show something is in J_m, you need to explicitly show that it is a multiple of m

Answer 82

m[yr]

Answer 83

b = ym

br = ym(r)
= m(yr)
\(\in \) J_m

Answer 84

which means for this question...

Prove that every integral ideal J is indentical with J_m for some m.

we need to compare the results for the integral ideal J version and the integral ideal with J_m for some m. Which means both integral idea J and J_m for some m have something in common right?

Answer 85

Like suppose J=J_m ?

Answer 86

then the set of integers J (integral ideal) is the same as the set of integers J_m (integral ideal). It's like we're going back to the previous question on this.

Answer 87

this looks more involved... i gtg for now wil be back in 2 hours @BSwan

Answer 88

I think the least integer principle is needed too which is every non-empty set of positive integers has a least element.

Ok so we know that the set has elements...only positive ones...and it's small

Answer 89

so some least positive integer number must be in J and J_m for both of them to be equal to each other.

Answer 90

you always need to think that
\(j_m\subseteq j\) according to both definition :)

Answer 91

set theory now!!!!

Answer 92

bhahaha yeah :P
this is all set theory btw

Answer 93

so j_m is a subset of j
\[(\forall x) [x \in j_m \implies x \in J]\]

Answer 94

ahhh... \[j_m\] is contained in J

Answer 95

we need to only consider the elements in J_m and J... which are certain least positive integers.

Answer 96

yeah , in other word you just need to show that
j_m is isomorphism on j , of the operation rm on j

Answer 97

oh great =__________= isomorphic... one of my weak spots.