Question

What is Euclid division lemma prove

Answer 1

$\huge\mathfrak\red{Answer:-}$

A Euclids division lemma is a proven statement which is used to prove other statements.

a = bq + r , 0 ≤ r ≤ b. In fact, this holds for every pair of positive integers as proved in the following lemma.

Euclids division lemma : Let ‘a’ and ‘b’ be any two positive integers. Then there exist unique integers ‘q’ and ‘r’ such that

a = bq + r, 0 ≤ r ≤ b.

If b | a, then r=0. Otherwise, ‘r’ satisfies the stronger inequality 0 ≤ r ≤ b.

Proof:-

Consider the following arithmetic progression

.., a – 3b, a – 2b, a – b, a, a + b, a + 2b, a + 3b,..

Clearly, it is an arithmetic progression with common difference ‘b’.

Let ‘r’ be the smallest non-negative term of this arithmetic progression. Then, there exists a non-negative integer ‘q’ such that,

a – bq = r ⇒ a = bq + r

As, r is the smallest non-negative integer satisfying the above result. Therefore, 0 ≤ r ≤ b

Thus, we have

a = bq1 + r1 , 0 ≤ r1 ≤ b

We shall now prove that r1 = r and q1 = q

We have,

a = bq + r and a = bq1 + r1

⇒ bq + r = bq1 + r1

⇒ r1 – r = bq1 – bq

⇒ r1 – r = b(q1 – q)

⇒ b | r1 – r

⇒ r1 – r = 0 [ since 0 ≤ r ≤ b and 0 ≤ r1 ≤ b ⇒ 0 ≤ r1 - r ≤ b ]

⇒ r1 = r

Now, r1 = r

⇒ -r1 = r

⇒ a – r1 = a – r

⇒ bq1 = bq

⇒ q1 = q Hence,

a = bq + r, 0≤ r ≤ b is unique.

Answer 2

Answer:

ᴍɪss ᴍᴀsᴛᴇʀᴍɪɴᴅ~❤️

ɪɴ ɴᴜᴍʙᴇʀ ᴛʜᴇᴏʀʏ, ᴇᴜᴄʟɪᴅ's ʟᴇᴍᴍᴀ ɪs ᴀ ʟᴇᴍᴍᴀ ᴛʜᴀᴛ ᴄᴀᴘᴛᴜʀᴇs ᴀ ғᴜɴᴅᴀᴍᴇɴᴛᴀʟ ᴘʀᴏᴘᴇʀᴛʏ ᴏғ ᴘʀɪᴍᴇ ɴᴜᴍʙᴇʀs, ɴᴀᴍᴇʟʏ: ᴇᴜᴄʟɪᴅ's ʟᴇᴍᴍᴀ — ɪғ ᴀ ᴘʀɪᴍᴇ ᴘ ᴅɪᴠɪᴅᴇs ᴛʜᴇ ᴘʀᴏᴅᴜᴄᴛ ᴀʙ ᴏғ ᴛᴡᴏ ɪɴᴛᴇɢᴇʀs ᴀ ᴀɴᴅ ʙ, ᴛʜᴇɴ ᴘ ᴍᴜsᴛ ᴅɪᴠɪᴅᴇ ᴀᴛ ʟᴇᴀsᴛ ᴏɴᴇ ᴏғ ᴛʜᴏsᴇ ɪɴᴛᴇɢᴇʀs ᴀ ᴀɴᴅ ʙ.