elementary-number-theory

[normal heart]

ok not that many steps, but you can see for p=11 the value of r is 6, and for p=13 the value of r is 6 as well

[sacred junco]

Yeah

[normal heart]

For p=11, r=p-((p-1)/2), while for p=13, r=(p-1)/2

this discrepancy is because of the fact that if p=11, p is congruent to -1 mod 4, so (p-1)/2 is odd, so p-(p-1)/2 is even

and in this list we are only considering even numbers in left hand side of the congruence, so we take r=p-(p-1)/2 in this case

for p=13, p is congruent to 1 mod 4, so (p-1)/2 is even, so we take r=(p-1)/2 in this case

[sacred junco]

Oh okay makes sense

How did they get the last equality?

[normal heart]

dividing ((p-1)/2)! both sides

if that's what you're asking

[sacred junco]

This one

2x4x6x...(p-1) changed to 2^((p-1)/2)((p-1)/2)!

and 1+2+3... to (p^2-1)/8

[normal heart]

factoring a 2 out of each term

there are (p-1)/2 terms so you have 2^((p-1)/2)

and you're left with 1x2x3x...x(p-1)/2 which is ((p-1)/2)!

[normal heart]

1+2+3+4+...+(p-1)/2=1/2*((p-1)/2)*((p+1)/2)

just using the formula 1+2+...+n=n(n+1)/2

[sacred junco]

Oh gauss sum

That's the last step

The implications are not clear

But Euler's criterion is clear

[normal heart]

which implications

[sacred junco]

From top

and the equation

[normal heart]

.

to get the equation

since p cannot divide the factorial

[sacred junco]

Oh yeah lol

I thought ((p-1)/2)! stands for something else

But it's just a requirement to divide both sides without getting division by 0

[normal heart]

yes

[sacred junco]

I'll skip gauss' proof and Quadratic reciprocity law proof for now and move on to the applications.
if we have (219|383) then we can use the multiplicative property to get (3|383)(73|383) now it says
(3|383) = (383|3)(-1)^((383-1)(3-1)/4)

What did they do exactly here

(-1)^((383-1)(3-1)/4) looks like (383|3)(3|383) to me so all together
(3|383)(383|3)(3|383)

[celest cloud]

is this s good way to write the totient function

$\phi(n)=\sum_{{a:(a,n)=1}} 1$

[sterile pumice]

mymathyourmath

[celest cloud]

im doing some formal notes on numb theo and gonna lead into some ergoc theory/p adic stuff

[leaden swan]

*a<n

[celest cloud]

here (a,n) denotes GCD

coprime 1 implies a<n

[leaden swan]

Not necessarily

Consider 5 and 11

11>5

[celest cloud]

ah

duih

cannot beliebve i forgot that

so $\phi(n)=\sum_{{a:a<n, (a,n)=1}} 1$

[sterile pumice]

mymathyourmath

[leaden swan]

Looks fine

[celest cloud]

cool thx

[leaden swan]

Well technically a<=n

Because phi(1)

[noble obsidian]

Could one possibly see if they notice any pattern for:

1 - ((n-x)/(n+1))^n = ((x+1)n/(n+1))^n

n is natural and x is in (-1, n)

[noble obsidian]

its worth noting that if we extend n to be negative then the limit as x approaches -1 then the intersection approaches -1 is 1 - phi

[fluid jolt]

Hello, Could Anyone recommend me some books for learning differential equations from basic, elementary?

[normal heart]

#odes-and-pdes

[sacred junco]

i have an exercise to prove that sum of terms in newtons binomial is $ 2^{n}$, in the answer there is that letting a=b=1 so $(a+b)^{n} = [ \sum_{k=0}^{n} \binom{n}{k} = 2^{n}$ but is this really enough?

[sterile pumice]

MrTrim
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[normal heart]

Yes, but I doubt it is intended

I think the intended way is probably double counting

[sacred junco]

double counting?

first i wanted to prove this by induction but man i don't want to write so much

[normal heart]

which book/course did you see this problem in?

[sacred junco]

so i looked up the answer and there was: "let a=b=1"

[normal heart]

different courses have different intended answers for this problem

[sacred junco]

it's a calculus book but in the first chapter there is some combinatorics, induction, logic, sets

[normal heart]

I think the intended way is double counting then

Consider a bag with n distinct items, and you grab however many items you like at once. How many different combinations are there?

[sacred junco]

umm 2^n because i can grab n items and n combinations of items idk?

[normal heart]

yes

count in another way now

consider the case where you grab k items, in a bag with n distinct items (where 0 <= k <= n)

how many different combinations are there?

[sacred junco]

k^n no?

[normal heart]

without replacement

so you just grab k items at once

[sacred junco]

idk man

[normal heart]

it should be nCk

n choose k

you should've learnt n choose k in the combinatorics part of the book, no?

[sacred junco]

yea ofc but it's just definition there one formula for n+1 chose k

[normal heart]

the book didn't explain what n choose k means?

i doubt they could call that combinatorics if they didn't even say that

[sacred junco]

yea it's just one chapter for newton binomial

[normal heart]

how much combinatorics did they teach

[sacred junco]

induction is considered in combinatorics yea?

[normal heart]

I'd hardly count that as combinatorics

Ok, so they didn't teach combinatorics then

Did they teach binomial theorem then?

[sacred junco]

yes

[normal heart]

How did they prove binomial theorem

[sacred junco]

the entire chapter is resolved around it

[sacred junco]

they didn't

[normal heart]

.

...

[sacred junco]

it's writen "this formula can be proven by mathematical induction and proving formula for coefficients"

[leaden swan]

Think of in terms of choices

[normal heart]

ok then probably the intended solution is binomial theorem then, letting a=b=1 is fine

[leaden swan]

nvm

[normal heart]

though this book is quite funny

[leaden swan]

Which book is this

[sacred junco]

it's polish book

"mathematical analysis in exercises"

[flat wind]

Could anyone give a hint? Here r_2(n) is the function that gives the number of representations of n as the sum of 2 squares

[errant otter]

I could run through the inductive proof with u rn if you'd like tho it ain't rlly gonna help with your understanding of nCr

I'll just explain on nCr before doing the inductive proof if you'd like. understanding nCr would make it easier to grasp ig

[quaint gate]

yea so there's multiple ways of doing the problems involving binomial theorem, one way is to produce a combinatorial proof, the other is just usual analysis, set theoretic way, either induction or just some formula (in this case just the binomial theorem formula), i've also seen some geometric proofs to combinatorial problems, you should try proving the binomila theorem yerself but #discrete-math message here's a proof and there's a more advanced proof just below this one too

[sacred junco]

yea that would help i was just given a formula but i don't know why it's so important

[errant otter]

okie great!

so lemme explain to the best of my ability

here we go

so first things first let's ask the question how many ways can we arrange 4 items?

ok perhaps a simpler example: I have 3 ties and 4 shirts. How many possible combinations of shirt + tie can I wear?

[sacred junco]

yeah well 3

[errant otter]

why 3?

[sacred junco]

because you can arrange 1 tie to 1 shirt and you will have 1 shirt left

oh wait

[errant otter]

Mmmm.... not quite

[sacred junco]

i missunderstund

i think

[errant otter]

XD I think u saw it

Ok so

think of it this way

I have ties A, B and C.

and shirts 1, 2, 3, 4

so A can be worn with 1, 2, 3, 4

[sacred junco]

ye ye i assumed they were the same ties and the same shirts

[errant otter]

B can be worn with ... and C

so the total number of combinations is?

[sacred junco]

12

[errant otter]

yes

okay, now let's look at a different qn

so we have 4 objects, A, B C D. How many can we arrange them?

let's start by picking A as our 1st object

[sacred junco]

wait what how many can we arrange them?

[errant otter]

yeah

like

ABCD, ABDC, ACDB, CADB...

[sacred junco]

ok ok my english went dumb

so you have 4 objects and you can swap between 4 places so it's 16 combinations no?

[errant otter]

Mmmm, not quite. Think of it this way: I have objects A, B, C, D. How many choices do I have for my 1st object?

like, how many possible objects can I pick to be the 1st one I'm arranging?

[sacred junco]

OHH

[errant otter]

so it's 4 right?

[sacred junco]

well for the 1st you have 4 yeah

[errant otter]

what abt the 2nd object?

[sacred junco]

OHHHHHHHHHH

so its 4!

[errant otter]

yes

so to generalise it

[sacred junco]

ohhhhh

[errant otter]

for n objects

we can arrange it n! ways

NOW but what if I asked

how many unique ways can I arrange 2 items out of the 4 objects?
like
AB, AC, AD, CD...

[sacred junco]

well i assume it's 4C2 because you are explaining binomial

[errant otter]

U could list it out

actually... not quite. that's combinations. What I'm asking for is the number of permutations

[sacred junco]

mh

[errant otter]

the difference is that for permutation order does matter while for combinations order doesn;t
That meaning, AB and BA is counted as 1 for combinations
AB and BA are considered 2 different arrangements for perumtations

[sacred junco]

oh

[errant otter]

in our case

we want permutations

[sacred junco]

so 4 are starting with A

[errant otter]

since AB is different from BA

yes

[sacred junco]

4 with B

4 with C

and 4 with D

[errant otter]

Mmm... not quite. Just think of it this way-
We only allow 2 objects to be picked.
For our first object we have 4 possible options
for our 2nd we have 3.
so it's just- 4*3

let's do a sanity check

and see if that's right

AB, AC, AD
BA, BC, BD
CA, CB, CD
DA, DB, DC

[sacred junco]

no AA?

[errant otter]

seems correct?

[errant otter]

we aren't picking the same object twice

[sacred junco]

oh oke

[errant otter]

if we are though

can u think of how many combinations there'll be?

permutations*

[sacred junco]

yeah 16

[errant otter]

mhm

it's just

n^(number of elements which we pick)

why?

[sacred junco]

ohhhhh

[errant otter]

well our first object, we have n choices.
2nd? also n

and so on

[errant otter]

but that aside, this is where we finally throw in a permutation formula

n!/(n-r)! where r is the number of things we "allow" in each group

why?

don't you realise that it's just anotehr way of re-expressing

4*3*2*1, except we remove the last 2 terms since we only look at the first 2

so to "remove" teh last 2 terms from 4!

we just divide it by the factorial of the number of terms we dgaf abt

let's say from a group of 10 things we want to see how many ways we can arrange 4 objects

[sacred junco]

ohhh so that's why it's called choose?

[errant otter]

so we know it's just 10(9)(8)(7)

[sacred junco]

because we choose the terms that we are "removing"

[errant otter]

yeah

[sacred junco]

lol

[errant otter]

but now

we finally talk about
combinations

so we know the number of permuations to be

n!/(n-r)!

but we don't want this!

there's some excess terms

which are considered the same

since AB = BA when we count possible combinations

while for permutations we treat them seprartely

so yknow, it's quite the annoying issue. How would we count the number of these "repeated" elements?

[sacred junco]

mhm so permutations are useful i assume for like counting numbers because 12 is not 21

[errant otter]

mhm

but for combinations, it's usefulbecause

for example the binomial theorem whichj we're gonna get at

xy = yx

so we WANT them to be the "same"

when we "add them up"

let's do an easy one to demonstrate what I mean

wiki has a rather good example so ima steal that

ignore the binomial coefficient

we'll get tehre

but this illustrates the idea of the case where we want xy and yx to be counted together and not separately

[queen summit]

Guys I can't post in help

[errant otter]

check channels and roles

[sacred junco]

mhm

[errant otter]

okay! nice
But the qn is HOW DO WE ELIMINATE THOSE STOOOPID REPEATED TERMS IN OUR PERMUTATIONS

let's break this down

and use the same example earlier

4 items, choose 2, but this time the order doesn't matter

AB, AC, AD
BA, BC, BD
CA, CB, CD
DA, DB, DC
can you see a pattern on which terms are repeated?

AB is repeated in BA. AC repeated as CA. AD as DA.

[sacred junco]

oh like that

[errant otter]

BC is repeated as CB, BD is repeated as DB

[sacred junco]

yeah i see

its like lines

[queen summit]

I wish I am good at math 🙁

[errant otter]

so how can I make this into a formula?

[sacred junco]

wait im thinking

[errant otter]

sure sure

[sacred junco]

so we from the group of 4 items we want to arrange into 2 so
4321 but we need 43 s 4 choose 2 but idk i feel like im missig something here

[errant otter]

it may be hard to see since this is a bad example, cuz the number of stuff we're choosing is the number of stuff we're nto counting, so ima illustrate it with 5 variables and still pick 2

AB AC AD AE
BA BC BD BE
CA CB CD CE
DA DB DC DE
EA EB EC ED

okay now

ok that's not the best way to observe it-

[sacred junco]

take your time

[errant otter]

sry I myself find it hard to word my thoughts

notice that for each of the possible permutation, we have r! number of repeating terms. In other words, the permutation we have that it "creates" r! number of repeated elements.... Um, how do I explain...

AH

Imagine I counted the permutations of n items with k elements per group.
any group of k elements have been counted k! times, which you have to compensate for.
So what does this imply abt the formula? @sacred junco
Do you understand what I mean by this?

[vestal hearth]

hello guys.... I had a question

[errant otter]

[white lion]

Hey had a question about a proof for this theorem

My first question is that how did the author come to the conclusion that m/2^n-1 is a divisor of m

[normal heart]

Note (2^n-1)*m/(2^n-1)=m, and since you proved m/(2^n-1) is an integer, we have m/(2^n-1) is a divisor of m

[white lion]

My second question is regarding it says it proves that 0(m) is a prime by demonstrating it only has 2 divisors, but how do we know we exhausted all the divisors and that m/2^n-1 is not itself the sum of other divisors, for example the sum of the divisors of 6 = 1 + 2 + 3 + 6 can also be written as 6+ 3 + (1+2) = 6 + 3 + 3

[normal heart]

Since $m/(2^n-1)$ is a divisor, we must have $$\sigma(m) \geq m+\frac{m}{2^n-1}.$$

[sterile pumice]

cflau_

cflau_

[white lion]

Thanks, I get that part but how do we know $/frac{m}{2^n-1}$ is itself not the sum of other divisors and just so happens also to be a divisor of m

$\frac{m}{2^n-1}$

[sterile pumice]

jayzsparrow

[white lion]

@normal heart

[normal heart]

we don't immediately know, but from that inequality, we see that there can be no other factors

since if there were any, the inequality would be strict

but we see that it's indeed an equality, so the inequality cannot be strict

in other words there aren't other factors of sigma(m) other than m and m/(2^n-1)

[white lion]

@normal heart why would the inequality be strict if there were other factors?

[normal heart]

We have sigma(m)=m+m/(2^n-1)+other factors

if there were other factors

since m/(2^n-1) is a factor of m, it must be a term of its own in the sum

[white lion]

Ok I see, but what if m/(2^n-1) = a+b such that a and b are also divisors of m then sigma(m)= m + m/(2^n-1) = m+ a + b

[normal heart]

if a and b are also divisors then we have sigma(m) >= m+m/(2^n-1)+a+b

since sigma(m) adds together all divisors of m

[white lion]

right

@normal heart Thanks for taking your time to anwser my stupid questions appreciate it I think i got it now 🙂

[fervent grove]

Let $s_2(n)$ denote the sum of the bits of $n$. Is
[\limsup_{n\to\infty}\frac{s_2\left(n^2\right)}{s_2(n)}]
finite?

[sterile pumice]

dfoiler

[fervent grove]

would also be interested if it's bounded (or converges?) for $n$ of the form $2^{k+1}-1$. approximately speaking, this should be a measure of how ``random'' the bits of $\sqrt{2}$ behave \ldots

[sterile pumice]

dfoiler

[white lion]

can anyone help me find a proof for this question? Im trying to figure out how for given primes p,qif p>q>5 then p^2-q^2 is a multiple of 24 or 24|p^2-q^2

Im supposed to use the fact that if (a,b_i)=1 for i= 1,2,3, . . . , n then (a,b_1 x b_2 x . . . x b_n)=1

[dusty dragon]

try showing that 3 divides p^2 - q^2 and 8 divides p^2 - q^2

for the first part, note that p, q are primes greater than 3 so p, q are either congruent to 1 or 2 mod 3; what does this tell you about p^2 and q^2?

for the second part, p and q are odd so what can you say about p^2 and q^2 modulo 8?

[loud moon]

the limit is not finite, for example for every positive integer k > 1, select n as the number which in binary has its (i!)th bit set for 1 <= i <= k, it is easy to see that n has k bits set but n^2 will have k(k + 1)/2 - 1 bits set, and the result follows as k -> infinity. I think any construction with the set bits of n sufficiently far apart is enough to force the term inside the limit to be arbitrarily large

[distant sandal]

stuck

[errant otter]

if x had 3^3 as one of it's factors it's GCD would include 3^3. same with 7

[distant sandal]

But if I let y = 3

then the gcd would be similar to 3^1

[errant otter]

if you did so then the GCD of x and y couldn't be > 3.

[errant otter]

wdym similar

[distant sandal]

if I choose x=3^3 and y=3^1 then the gcd could be 3^1

[errant otter]

right...

mb

I suppose you can't assume anything abt y

.. ngl this is weird

[distant sandal]

I suppose I could try asking my teachers this question

[errant otter]

could the property that xy/gcd = lcm help here?

[distant sandal]

I dont think so

[errant otter]

yeah doesn't seem like it

[distant sandal]

But the xy/gcd = lcm is helpful for part b

[errant otter]

funny....

I have this feeling that the marking system is wrong

[distant sandal]

Same

[errant otter]

do you "lose" anything by clicking on "reveal answers"?

[distant sandal]

Nah it's a practice paper

[dusty dragon]

ah this looks familiar

[errant otter]

well u could ask your teacher abt it, or just reveal it. Choice's up to u

[dusty dragon]

yeah so 2^2 is not possible; otherwise, it must appear in either the gcd or the lcm

think about the gcd and lcm in terms of the prime factorisation

[errant otter]

ah.

right....

@distant sandal what opengang's trying to say is that since x can't have 2^2 since otherwise the GCD won't have 2^3 I think

or um

did I get that wrong

[dusty dragon]

Consider x = p_1^{a_1} ... p_n^{a_n} and y = p_1^{b_1} ... p_n^{b_n}. How could you write the gcd and the lcm in terms of the prime factorisations of x and y?

This will tell what powers for each of the primes are possible to maintain the gcd and lcm

[errant otter]

ah

right right

I'm thinking

||LCM/11||

is that right?

[dusty dragon]

🤔

[distant sandal]

The 2^2 thing not being possible does make sense now

[dusty dragon]

that does not look right

[errant otter]

........

I suck

wait

make it 2^3

not 2

... probably still wrong

[dusty dragon]

even then, 11 is too big of a number to divide

you can divide by something smaller

[distant sandal]

I saw these in math books but im not sure how i can apply it to this problem

[dusty dragon]

yup

so

let's say that x does not contain 2^3

what power of 2 must x contain?

[errant otter]

y u mean?

[dusty dragon]

either

[errant otter]

but if x doesn't contain 2^3 y must have 2^3

[dusty dragon]

yup

but you also know what power of 2 x contains

because of the gcd

[errant otter]

but subsequently if so gcd would have 2^2 or 2^1 in it

which isn't true

[dusty dragon]

yup

so the power of 2 would have to be 0

in x

[dusty dragon]

otherwise, the gcd would contain some power of 2

you can divide by something smaller than 8

[distant sandal]

I'll try x=7 and y=7^2

[dusty dragon]

it should be 2^3 * 3^3 * 5^2 * 7 * 11^2

[errant otter]

u mean for x?

[dusty dragon]

dividing by a power of 2 is dividing by 2^3 = 8,
dividing by a power of 3 is dividing by 3^2 = 9,
dividing by a power of 5 is dividing by 5^2 = 25,
dividing by a power of 7 is dividing by 7^1 = 7,
dividing by a power of 11 is dividing by 11^0 = 1 but this implies that x = lcm(x, y)

[dusty dragon]

yeh

[errant otter]

damn.

geez...

I've forgotten how all these prime factorisation GCD stuff works

gonna have to brush up on it.

sorry for being misleading

[dusty dragon]

I've had to teach this multiple times

so

💀

[errant otter]

average HS teacher moment

[dusty dragon]

first year uni math moment

pensive

but yeah, I remember looking at this problem for the first time and getting stuck for about 5 mins

[errant otter]

honestly most of this is just guess and check isn't it?

[dusty dragon]

nah there's a systematic way to doing it

you just need to know how the gcd and lcm relate to each other in terms of the prime factorisation

[errant otter]

ok new programming exercise for me

[white lion]

@dusty dragon the issue is this chapter preceded the one on congruences although I’m already familiar with modulo n and I can’t take for granted that all prime except for 2 are odd because I havent proved it in a theorem or corollary in the chapter.

[normal heart]

??

[gloomy minnow]

I’m posting this in both #groups-rings-fields and #elementary-number-theory as my question relates to both.

does anyone know of a short pdf document (or perhaps an appendix of some book) that sums up all the number theory ‘facts’ (theorems and definitions) needed for algebra? Preferably it should include proofs, but I’d be fine with accepting many ‘obvious’ statements without proof like the division algorithm and whatnot.

[white lion]

Im tyring to prove that p^2-q^2 is a mutliple of 24 with the only hint being that I need to use the fact that if (a,b_i)=1 for i= 1,2,3,...,n then (a,b_1 x b_2 x . . . x b_n)= 1

[normal heart]

what's p and q

[normal heart]

this is trivial from the definition of prime numbers...

I couldn't have imagined how you know mod but can't use the fact that the only even prime is 2

[dusty dragon]

Every even number has a factor of 2, so if a prime is even, it must be 2

[white lion]

I know it's trivial but from the book I'm reading it hasn't been proved and it hasn't used that fact in any of the proofs thus far

[normal heart]

I highly doubt it hasn't used this fact

[white lion]

I can't take mod for granted also

well I don't know what to say, it hasn't ive done all the excercises so

[normal heart]

but just because the book doesn't mention it doesn't mean you can't use it, your book hasn't defined addition and multplication of natural numbers probably and I doubt you wouldn't allow yourself to use it

especially when it's something as trivial as there only being one even prime

[white lion]

it's fine Im just trying to figure out how I can use the fact that "if (a,b_i) =1 for i= 1,2,. . . , n then (a,b_1 x b_2 x . . . x b_n)=1" to show that if p and q are primes such that p>/=q>/=5 then 24|p^2-q^2.

@normal heart

[mighty fable]

DOes +-1 divide every integer?

[still flare]

Yes

[dusty hound]

If a < b a,b in reals, then for n in N sufficiently large, could it be possible for any number s in N such that there exists a n that makes the following true
nb > na + s
And how would I prove that?
Example:
s = 3000, a= 5, b = 6
6(n) > 5(n) + 3000
n = 4000 satisfies as 24000 > 23000

[dusty dragon]

In other words, you require that n > s/(b - a)

[dusty hound]

Oh ur right so I just choose n such that its greater than s/(b-a)

[dusty dragon]

yup

[dusty hound]

Thanks lol

So, altogether... would this count as a proof?
If a,b in reals where a < b and an arbitrary s in N is chosen, then there exists n in N such that
nb > na + s
where n is chosen to be a number greater than s/(b-a) because
nb > na + s
nb - na > s
n(b - a ) > s
n > s/(b-a)
and by the archimedes property of the naturals, there exists such n in N.

Like this?

[open mist]

On paper use equivalence symbols for the computation

But otherwise yes

[dusty hound]

Thanks!

[sly ibex]

On a blackboard there is initally written the integer 1. If the current number on the board is x, it can be replaced by one of the following numbers: x - 5, x + 10 or 3x +1. Is it possible to reach the number by repeating these operations 2? Can this be solved using modular arithmetic? We can get to 2 from x - 5, x + 10 or 3x +1 if we can get to 7, -8 or 1/3. The last one is impossible i think.

[west glade]

1/3 is clearly impossible as you can only reach integers. if x is on the blackboard and y is the new number, what can y mod 5 be (depending on x mod 5)?

[sly ibex]

we have y = x - 5, x + 10 or 3x + 1 so mod 5 either y = x, or 3x + 1

[west glade]

we start with x=1. so at each step we can either get x again or 3x+1. what are all the possible values we can get

[sly ibex]

1 or 4?

[lilac elk]

So u want a finite nunber of steps that lead from 1 to 2 using those 3 operation. Right?

[west glade]

and from 4 we can get which values?

[chrome bluff]

what do you mean by these operations 2?

[sly ibex]

Sorry I meant reach number 2 by these operations

[sly ibex]

wdym by getting values from 4?

[chrome bluff]

So you wanna get from 1 to 2?

[sly ibex]

Yeah starting from 1 you can replace it by any one of the three numbers and the question is wether you can get to 2.

[normal heart]

use the mod 5 method suggested above

[sly ibex]

Is it just since the values are always 1 or 4 mod 5 and never 2 we can't get to 2?

[west glade]

well nearly except they aren't only 1 or 4

[loud maple]

No, but the values are always 0,1,3 or 4 mod 5
Applying the 3x+1 operation repeatedly, we get:
1 -> 4 -> 13 -> 40 -> 121

So we get all values mod 5 except 2

[torn escarp]

for fun, $f(x)=ax+b$ has a closed form for the nth iteration, $$f^n(x) = a^nx + \frac{a^n-1}{a-1}b$$
our case is $a=3$, $b=1$ and $x=1$ modulo 5, so we end up with this exponential, which can only cycle through at most 4 things, so it's impossible for it to hit all 5 remainders

[sterile pumice]

merosity

[static cedar]

I'll send my prove for odd cases..

[errant otter]

Nani

[static cedar]

Is this proof correct?? If yes then how can prove the same thing for "even" case

[glass knoll]

bro rly said nani 💀💀

[torn escarp]

if n=2m then epsilon = m mod 2, so if m is odd we're done

[static cedar]

?

[torn escarp]

!

[static cedar]

What does mod mean?

I've just attended 1 lec of numbers theory

[torn escarp]

ah

x=y mod z means z | x-y

I feel like that's pretty terse but I'm sleepy and about to go

[static cedar]

I dont get it quite get it.... but alr

[errant otter]

x = y mod z means x = qz + y where q is the quotient, y the remainder

[static cedar]

So if like I had to write x+y | 5

How would I write it??

[errant otter]

x+y | 5 means x+y divides 5

in other words

x+y = 0 mod 5

[static cedar]

Alr

[still flare]

This is wrong

[errant otter]

ouch.

oh

I see why

💀

Um

ummmm

I think um

but even then (after I edited) it doesn't show teh idea of congurence

[still flare]

Modular arithmetic a priori has nothing to do with remainders, too. E.g., 7 = 12 mod 5 is totally correct.

[errant otter]

mhm

[still flare]

Merosity’s definition was correct, so let’s stick with that.

[errant otter]

yea

[robust wharf]

smart

if n is divisible by a higher power of 2, just reduce modulo that power?

or

hm

[static cedar]

Does the proof work?

[glass knoll]

yes

[static cedar]

Alr Thanks

[fiery zenith]

i dont find it clear what your 2 cases are

presumably n odd or even

[static cedar]

First n is odd and second n is even

[prime gust]

i tried solving 3x=6 mod 10 and something about it confuses me. 3x=6 mod 10 --> x=2 mod 10 and that is the solution but notice that 3x=6 mod 10 also means by multiplying both sides by 4 that 12x = 24 mod 10 or 10x +2x = 10 + 10 +4 mod 10 simply meaning 2x= 4 mod 10 but then we could divide both sides by 2 and get x = 2 mod 5 is a solution but when putting for instance 7 which is 7=2 mod 5 it is not a solution to 3x=6 mod 10 since 3*7=21=1 mod 10 and 1=6 mod 10 is nonsense. So I am pretty confused as to why it happened i thought that the multiplication by 4 is a mistake but there is a well known statement that says if a= b mod n then ca=cb mod n.

[random sand]

It implies that x=2 mod 5, but that doesn’t mean x=2 mod 5 implies 3x=6 mod 10

[prime gust]

it implies that x must be of the form x=5k+2 for some k

[random sand]

But not all k

Evidently

[prime gust]

i know but then why would i get x = 2 mod 5 i mean while solving i used regular rules and didnt break nothing yet it looks like this solution is wrong so why would i get this solution even though its wrong

[random sand]

It’s a correct implication, but that’s also like saying

3x = 6

So 0x = 0 because we multiply by zero

Doesn’t mean every solution to the second is a solution to the first

But every solution to the first is a solution to the second

[verbal cedar]

you multiplied by a zero divisor, and then divided it out. that's why.

3x=6 mod 10 has exactly one solution: x=2
but when you multiply by 4 (a zero divisor) you get
2x=4 mod 10, which has two solutions x=2,7
you created an extra solution because you did an uninvertible action

[prime gust]

but i didnt multiply by 0

[verbal cedar]

it's a zero divisor

[prime gust]

what do you mean

4?

[verbal cedar]

4*5=0 mod 10

it's the equivalent of multiplying by a singular matrix in linear algebra

[prime gust]

i did 3x = 6 mod 4 to 12x = 24 mod 4

mod 10*

[verbal cedar]

yes, and the second has more solutions than the first

[random sand]

Yes, the left implies the right

But it’s one way

[verbal cedar]

you multiplied by a zero divisor, and got more solutions

that's what you did wrong

[random sand]

x^2 = 1 doesn’t mean x=1 after all

Even if it works in the other direction

[prime gust]

I know what you mean but how come 4 is a zero divisor i mean its not like i did 3x= 6 mod 10 and then multiplyed it by 10 or 20

i multiplyed by 4

[random sand]

4 * 5 = 0

So you can’t really divide by 4

[prime gust]

where does the 5 comes from?

[random sand]

It’s an example

[prime gust]

oh

i mean

[verbal cedar]

mod 10 ofc

[prime gust]

i did 3x*4 =12x

[random sand]

Right right but context clear

[prime gust]

and 6*4=24

[random sand]

3*5 = 5 mod 10

So multiplying by 4 on top of that

Is not good

[prime gust]

but x is not 5

[verbal cedar]

but 7=2+5

[random sand]

5 going to zero is like exactly the issue you’re having

[verbal cedar]

4(3(7))=4(3(2+5))=4(3(2))+3(4)(5)=4+0=4(6) mod 10

that's why you get a second solution

[prime gust]

i mean what is wrong about doing 3x = 6 mod 10 and since 4 is not a zero divisor we can multiply both sides

[verbal cedar]

that is exactly 5 above your other solution

[random sand]

4 is a zero divisor

That’s the issue

[grizzled rapids]

Which part of 4 is a zero divisor are you not understanding?

[still flare]

4 * 5 = 0 mod 10

Hence, it is a zero divisor

[random sand]

a = b does imply f(a) = f(b), but not the other way around in general

[prime gust]

i get that 4*5= 0 mod 10 but i never multiplyed it by 5

[random sand]

But you can

And that’s why you get extra solutions

[still flare]

Do you know what it means to be a zero divisor?

[prime gust]

not quite

[still flare]

You could have said that ages ago!

[random sand]

It being a zero divisor is a bit of jargon that’s pretty much summed up by this line though

[still flare]

An element x is a zero divisor if there exists a nonzero element y such that xy = 0.

Hence 4 is a zero divisor, since 4 * 5 = 0 mod 10

Now here's a trick:

You cannot divide by zero divisors

e.g. 4 * 0 = 0 mod 10, and 4 * 5 = 0 mod 10, so if you have 4x = 0 mod 10, you cannot conclude that x = 0 mod 10, for example.

In general if 4x = 4y mod 10, you cannot conclude that x = y mod 10.

You divided by a zero divisor!

[prime gust]

i mean if 4x= 0 mod 10 then you can divide both sides by 2

and get 2x = 0 mod 5

[still flare]

2 is a zero divisor

(mod 10)

[random sand]

2 is also a zero divisor, since 2*5=0 (mod 10)

[still flare]

so you cannot divide by it

[prime gust]

do you guys know the book David.M.B number theory?

[verbal cedar]

it's also worth noting that the zero divisors and invertible elements partition the ring. that is, an element is invertible if and only if it is not a zero divisor. and a zero divisor is any element which is not coprime to the modulus.

[prime gust]

there is a statement here that if ca=cb mod n then a=b mod (n/d) where d=gcd(c,n)

[random sand]

Yes, that’s one way

[still flare]

Right, I see. You do get this weaker result.

[random sand]

it doesn’t let you go backwards

[prime gust]

ik

but there is also a statement that if a=b mod n then ca=cb mod n

cuz if n divides a-b

[still flare]

We know

[random sand]

But you acted like it did when you brought up being confused over the additional solutions

[still flare]

you don't have to explain this to us.

[prime gust]

of course it will divide c(a-b)

[random sand]

That’s both mod n

Not two different mods

[verbal cedar]

and here $x_0=0$ is the only solution. BUT because you divided by $2$ to get to that $\bmod{5}$ equation, the general solution is
$$x=0+5t,\quad 0\leq t<2$$

[sterile pumice]

nixxy nilpotent (raving lunatic)

[still flare]

a = b mod n does not imply, for example, that a = b mod 2n.

[prime gust]

ik

[still flare]

For example 0 = 5 mod 5 but 0 =/= 5 mod 10.

[verbal cedar]

giving x=0,5 to be solutions

[prime gust]

the second statement implies that 3x= 6 mod 10 can be equal to 12x = 24 mod 10

c=4

a=3 and b = 6

[grizzled rapids]

Are you trolling us? It is hard for me to tell if you are joking or not.

[prime gust]

absolutely not

[random sand]

It implies it yes, but it is not an “if and only if”

(-2)^2 = 2^2 after all

0*4 = 5*4 too

[prime gust]

so what you mean is if 3x= 6 mod 10 then x=2 mod 5 but not for every x=5k+2

because its not if and only if

[random sand]

Yes

[still flare]

I mean you can literally see this explicitly, for instance with x = 7.

[prime gust]

i know

[still flare]

That's k=1, if it's not clear

[prime gust]

i did it for x=7

[still flare]

So you should immediately see that what you claim isn't right

[prime gust]

i know that i could do that but i didnt quite understand why i couldnt

[random sand]

The original message where he mentions 7 as a problem explicitly

[prime gust]

i did understand that x=2 mod 10 means as well that x=2 mod 5 and x=2 mod 2

and then i knew that x-7 is false

x=7

it really confused me but thanks for helping me out!

just to get it clear in order to find a solution for a congrunce i must have if and only if steps right?

if i want to get a whole answer

like an equation

[verbal cedar]

you can only do invertible steps. that's a better way to phrase it

i.e. only multiply by invertible elements (i.e. not zero divisors)

[random sand]

Well, comparing x=2 mod 5 and x=0 mod 2 together, you do get the original x=2 mod 10

But you need both to rule out odd multiples of 5

But doing invertible steps is important

[prime gust]

the funny thing about this is that i never get to fully understand congruences rules i mean i am learning much complicated stuff in number theory but i always have problems in congruences xd the original equation i had to solve was 4x^3=3 mod 11

[random sand]

(You can make my argument more general and know exactly when it works later on)

Do you know when 4*a = 1 mod 11?

[prime gust]

i think it because once you multiply by d and if gcd(d,n)>1 n for mod n then it is a zero divisor right?

a = 1 mod 3

[random sand]

That works I think yeah

4*3 = 12 = 1 mod 11 ye?

That’s an invertible step

[verbal cedar]

just a note: you can divide by a zero divisor, but you have to do this to account for all the solutions you lose by doing so

[random sand]

So you can multiply by 3 or 4 and keep it iff, since you can invert it

[prime gust]

cause it ruins the uniqueness of the number in 10 divides 3x-6 once you multiply it by 4 it is obvious that 10 divides 4(3x-6) but it divides the 2 from the 10 and you get 5

if that makes sense

[analog raptor]

The product of some 48 natural numbers has exactly 10 prime divisors. Prove that among those numbers you can choose four whose product is a perfect square.

I have seen this problem somewhere and I don't think it's particularly hard but I just can't come up with a solution.

[buoyant mason]

hint: a natural number is a perfect square iff all the exponents in its prime factorization are even

i think it’s still pretty tricky though

[errant otter]

[analog raptor]

That is a pretty basic fact (that I know) but still I'm not sure how to formally do it

I just can't find a way to use the numbers 48 and 10, not sure where to even start

[torn escarp]

I'd probably try to do some kind of pigeon hole argument

[buoyant mason]

it allows you to treat the exponents on each of the 10 primes in each of the 48 numbers as 0 or 1

[still flare]

Here's an observation: 48 choose 2 = 1128 > 1024 = 2^10 ;)

[buoyant mason]

which adds an extra element of finiteness for pigeonhole principle

[still flare]

@analog raptor does this observation give you a hint as to where your pigeonhole argument should go?

You may need to do some casework to figure some edge cases out, fair warning.

[analog raptor]

Let me think a bit

[still flare]

I couldn't possibly allow that no

[still flare]

I know this is a good observation because 47 choose 2 < 2^10, so in fact for the argument I have in mind, 48 is the minimal example.

[analog raptor]

I understood, thanks a lot ❤️

[sacred junco]

Is 0^0 = 1 valid ?

[west glade]

no, at least not in general

in certain contexts, $0^0$ is defined to be $1$, eg to be able to write polynomials as $\sum_{k=0}^n a_k x^k$ instead of $a_0 + \sum_{k=1}^n a_k x^k$ and to still be valid for $x=0$

[sterile pumice]

denascite

[sacred junco]

But I think it's valid in general

But still

0/0 disturbs alot

Which is kinda cannot be defined

But still I think

0^0 = 1 in general if we think differently rather than thinking x^(m - n) = (x^m)/(x^n)

Which is true if x is not equal to 0

[patent acorn]

if you want to know what "0^0" is then look at how you're defining ^ and that will tell you what it is

[west glade]

well at the same time, 0^x=0 for all positive x

[sacred junco]

Yeah

[sacred junco]

But I think when it comes to base and exponent both to be 0 then it kinda changes meaning. For example in terms of complex numbers exponentiation does not mean repeated multiplication but rather than it means rotating with the complex argument. So I think it's the same thing with both base and exponent to be 0 ig?

[west glade]

well ok but imaginary part is 0 so no rotation in sight

[sterile pumice]

whoamiPwns

[sacred junco]

Wait

It got me wrong

I have to write it on paper ig?

[patent acorn]

$e^{0\ln(0)}$

[sterile pumice]

bee [it/its]

[west glade]

and now you run into another issue with 0*ln(0). aka 0*(-infty)

[sacred junco]

Yeah

[sacred junco]

That's what I meant

And I am thinking that it has a meaning

[sacred junco]

So we will take the reciprocal and we get 1/(e^0)

[normal heart]

?

[sacred junco]

So it is equals 1

[normal heart]

taking the reciprocal of what

why is 0*-infty=0?

[sacred junco]

-infinity must mean some negative number far away from 0 on number line

So

[normal heart]

no, infinity is not a number

[west glade]

ln(0) is undefined. the limit x->0 of ln(x) is -infty. you are running into all kinds of limit problems with approaches like this

limits of the form $\lim_{x\to 0} f(x)^{g(x)}$ where $f(x)\to 0$ and $g(x)\to 0$ can take on any value

[sterile pumice]

denascite

[west glade]

depending on which f and g you choose

[sacred junco]

I know but it is considered that infinity must be a very very large number which we don't know

That's why

[west glade]

infinity is not a number

[patent acorn]

...no it isn't

[sacred junco]

but I am choosing f and g both to be x

[west glade]

which is an arbitrary choice

[sacred junco]

Yeah, if f(x) = g(x) = x then we can tell that it can be f(x)^g(x) = 1 as x->0

[normal heart]

why not f(x)=exp(-1/x^2) and g(x)=x^2?

[sacred junco]

Then it will be 1/e

[normal heart]

so why can't I define 0^0 to be 1/e then

[sacred junco]

But we are taking f(x) and g(x) be arbitrary

[normal heart]

and so the limit f(x)^g(x) as x->0 (where f(x) ->0 and g(x) -> 0) can be anything

why must you take f(x)=g(x)=x and not f(x)=exp(-1/x^2), g(x)=x^2?

[wooden glen]

The point is that you cannot make a convincing argument for how 0^0 ought to be defined by considering that kind of limits, because the limit depends on exactly how the inputs converge to (0,0).

[sacred junco]

Because an identity function takes the input and spits that same input as output. And if we take some function which moves that input to different point then it will not be 1 anymore. Basically it depends what function you are taking as that limit

For example

[normal heart]

your point is to approach 0^0, so as long as both my f and g approach 0, it should be fine, no?

[wooden glen]

Fine in which sense? Since there is one choice of f and g where the limit is 1 and another choice where the limit is 1/e, we conclude that
lim_(x,y)->(0,0) x^y cannot exist.

(This is not the same as saying 0^0 cannot have a result, mind you).

[normal heart]

I know, I'm only rebutting @sacred junco

[wooden glen]

Sorry.

[sacred junco]

You put some number close to 0 to this. And that number close to 0 be squared and moved to some output space to some point which is even more close now. And due to its transformation it is not what it could give if we didn't have moved that input point.

[normal heart]

so?

i know the limit is different that's the whole point

but why must you choose f(x)=x and g(x)=x?

[sacred junco]

Because it will not disturb the input point. The position of input and output will be same in input and output spaces

[normal heart]

so what if it doesnt disturb the 'input point'?

and so what if it does?

[sacred junco]

Try to Think functions as a way to move throughout the input and output spaces

You will know.

f(x) as an identity function will not disturb very much that point

[west glade]

but why is it a problem if it disturbs the input space

its an arbitrary restriction to say that you cant do it. you havent given any argument other than "I dont want it"

[normal heart]

Your strategy to find 0^0 is by finding two functions f(x) and g(x) both converging to 0 as x approaches 0, and finding the limit f(x)^g(x) as x approaches 0. Why must you emphasize choosing f(x)=g(x)=x? In other words, why must you enforce the restriction 'not disturbing the input point'?

[sacred junco]

The reason behind this is my playful nature with this. I mean I tried to find that using a very well known logarithmic series as you know. The reason I thought to put f(x) = g(x) = x was because I stumbled over it while playing with limits and logarithmic series

Its all because I was just toying with identity function. And thought about what if we do x^x and put x to 0

Or make it approach to 0

[wooden glen]

So overall, the problem here is that you're trying to argue for a true conclusion (0^0 is usually defined to be 1) by an argument that is not convincing.

There are good reasons to define 0^0 in that way, but limits is not one of them.

[sacred junco]

But can we do it by logarithmic series
-ln(1-x) = x + (x^2)/2 + (x^3)/3 +...... Infinity

?

Because I did it by this logarithmic series only

So just asking if there is a way

By others perspective

By putting x = 1 we get a harmonic series

And by that harmonic series we can approach to the conclusion 0^0 = 1

[wooden glen]

That power series is correct, but I don't think it makes a meaningful argument either way about 0^0. It doesn't even have an x^0 term that we might need to plug x=0 into.

[sacred junco]

I know it is quite unconvincing

Very well

[torn escarp]

another fun case which is consistent with the choice $0^0=1$ is if you look at the binomial theorem, $$0^n = (1-1)^n = \sum_{k=0}^n \binom{n}{k}(-1)^k$$
When $n=0$ the sum becomes just $\binom{0}{0}=1$, when $n>0$.

[sterile pumice]

merosity

[sacred junco]

But I didn't use binomial theorem for that. I just used the logarithmic series and from that I got a harmonic series, which redirected me to write this

[sacred junco]

@torn escarp

[torn escarp]

never claimed you did

[grizzled rapids]

I do not understand how this conversation went on for 20 more minutes after this. This is the answer.

[pale fjord]

Wat is the solution to this:

@Dongster

[fervent grove]

the polynomial x*P(x)-1 has n+1 prescribed roots, allowing you to solve for P(x)

[prime gust]

if x<y<z form a primitive Pythagorean triple and a prime p divides z then p must be of the form 4k+1 is this statement true?

[errant otter]

!nosols

[rotund gust]

As a helper, please do not give out answers that could be copied as a homework solution. Have the student work through the problem themselves and guide them along the way.

[pure arch]

4,5,3,3,8,3,6,9,0,7,1,5,7,7,2,9,4,9,3,1,7,7,0,7,6,6,5,4,4,1,7,0,5,6,5,5,0,3,5,2,6,1,2,6,0,8,4,8,0,8,0,4,7,8,4,3,4,4,0,2,6,6,1,3,9,1,6 next ?

[sacred junco]

Quadratic reciprocity is confusing the hell out of me. How do you deduce this

From

Did they multiply both sides of the equation by (q/p) or something?

That doesn't seem the case

It feels like black magic

[normal heart]

yes

[west glade]

because (q/p) is 1 or -1, you can just multiply it on both sides and then (q/p)^2=1 on the right side

[sterile pumice]

jayzsparrow

[open mist]

,w phi(2773)

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by mateo713#0

[open mist]

,w factor 2005

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by mateo713#0

[errant otter]

Welp no euler throrem

[open mist]

159 = 21 mod 46
159 = 43 mod 58
2005 = 31 mod 47
2005 = -1 mod 59
By CRT,
x = 2005^159 = 31^21 mod 47
x = (-1)^43 mod 59 = -1 mod 59

That reduces the problem to finding 31^21 mod 47

[errant otter]

Geez

CRT

[open mist]

31^3 = 40 mod 47
40^7 = 38
31^18 = 38 mod 47

so then by solving the CRT equation, we get x

[errant otter]

Or better yet

,w 2005^159 (mod 2773)

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by kiameimon#0

[errant otter]

Wtf

That was fast

[torn escarp]

I suppose 18=2^4+2^1 means you don't have to do tooooo much extra work by repeated squaring

[open mist]

that's that

too

2 3 3

[torn escarp]

I see

[open mist]

as we know, when
x = 38 [47]
x = 58 [59]
47^59 = 1 hence we find 59 = 47+12 and 4*12 = 47 + 1, hence 4*59 - 5*47 = 1
Hence x = (-1)*(-5)*47 + 38*4*59 = 9203 = 884 mod 2773

[open mist]

I was undeniably faster

honestly that should be in your skillset by now anyways

[errant otter]

"Time is relative, all I rlly did was to compute it all 10cm Way from the event horizon of a black hole so as to slow time down to the point by the time I got out and returned the answer wolfram wouldn't even have computed one power"

[open mist]

it's subchapter 1 of chapter 1 of Knapp

[errant otter]

Every time I hear knapp being mentioned it gives me a feeling like a sting in the ass

[open mist]

it's basic undergrad stuff

should be next on your list

just like linalg

except arithmetic should go first

like Knapp did

it has some advantages when tackling polynomials of endomorphisms, to really make use of the Cayley-Hamilton theorem properly

among other things

[still flare]

Note to all beginners: books that say ‘elementary’ or ‘basic’ do not mean that their content is easy; it means that their content is fundamental to the subject!

Also some books are just shit

soz

And I'm sure they said it accurately

[errant otter]

[leaden swan]

Re: A course in Arithmetic

[pale fjord]

Ayo how do you simplify this: $f(x)=(2^a-1)(3^a-1)(4^a-1)...(x^a-1)\mod {m}$

[sterile pumice]

aSome1gussy

[pale fjord]

Where a, m and x are integers, m is a composition of two very large primes

[torn escarp]

there's some stuff you can do but I wouldn't expect to get a cute closed form

like boil down the exponents with euler's theorem and/or use the chinese remainder theorem

[pale fjord]

za le?

can you show me

[torn escarp]

might be a stretch to also try to use the lifting the exponent lemma

[torn escarp]

there's not much to show

the problem is too broad to write down a literal step like I'm describing, it'd be something you'd have to program or something but

why do you want to do this in the first place

[pale fjord]

they gave it to me from school

so i sorry don't know how to do

[torn escarp]

what have you learned

do you know euler's theorem or the chinese remainder theorem or is this the first time you've heard of it

[pale fjord]

I know both

But how to apply it.

[torn escarp]

does this problem have more info

can you post a screenshot/picture of the original question

[leaden swan]

You simply cannot

[verbal cedar]

<@&268886789983436800> ?

[loud moon]

well the case a = 1 is equivalent to computing a modular factorial which is known to be hard (at least as hard as factoring, and almost certainly harder) so this doesn’t bode well for your problem

[errant otter]

laughs in wilson theorem

heck this takes it a step further and makes it even more complicated

[odd atlas]

I did this problem just by observing that every 3rd number I was getting an even number

and then realize that 1022nd number is result of addition of an even and odd number

which gave the correct answer of 1

but I am wondering if there's some more standardized way to approach this

or there's something more I can see in it

[still flare]

If we look at everything mod 4, we get the sequence of remainders 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, .. which clearly repeats every 6 terms. We have 1022 is 2 mod 6 since 6 | 102, and so f_1022 = f_2 = 1 mod 4.

This works because modular arithmetic respects addition

[odd atlas]

yeah that's kinda more straightforward than how I did it lels

[errant otter]

bruh fibbonaci

[odd atlas]

how does one know how to approach it tho

[still flare]

You don't

[odd atlas]

it took me good 15 minutes to get the answer

hm?

[still flare]

I just tried something and it worked out. There is no way to tell how to prove something in general.

[odd atlas]

Before I tried to spot the mod 3 pattern, I wasted time on using the ratio and tree structures to find something lmaoooo

I certainly make dumb choices

tho

[still flare]

It's always a good idea to do the simplest thing first.

[errant otter]

https://tenor.com/view/thats-the-neat-part-you-dont-invincible-gif-27194608

[errant otter]

the ratio?

[still flare]

If you're using rational numbers to solve problems in modular arithmetic, something has probably gone wrong.

[errant otter]

me: uses generating functions to set up a diffeq, expresses f_n in a closed form and then apply mod and hope something pops out

[still flare]

Unfortunately you can't do that with exponential generating functions. e^x mod 4 doesn't mean very much.

[errant otter]

....

frick

😭

[still flare]

In any case I think even with a restricted class of ordinary generating functions where this works, you need some more theory on periodicity

[odd atlas]

yeah I should not have thought of it

Later I realized the fk I am doing

[still flare]

Being able to notice that is a learnable skill

[odd atlas]

I thought I'd get some cancellation and shit, but after writing it all down I realized it's not gonna get me anywhere

[errant otter]

relatable

[gilded breach]

Euclid's Lemma: If p is a prime, then whenever p divides a product ab, p divides at least one of a, b. Prove the converse, that any natural number having this property (for any pairs a, b) must be prime

The converse is, If p divides a product ab, and p divides at least one of a, b then p is a prime

This seems like a false statement

[patent acorn]

that's not the statement they intended

they want you to prove that if p has the property that for all ab, if p divides ab, then p divides at least one of a and b; then p is prime

[gilded breach]

Oh I see. Okay I'll try to prove it

Thank you

[fossil lynx]

Hey any good YouTube channel to study Number theory? Just getting started with it

[spring plume]

hi guys
i have heard that 0.999.... is considered exactly equal to 1
but if we do so then,
if we say
(n-1)/n =n/n (n=inf) (or 0.99.. =1)
n-1=n (multiply by inf) (could u say 1/uncountable infinity=0? no I guess 🤔)
that would be -1=0 so it should be 0.99... tending to 1?

[west glade]

1=0 is wrong

limits being equal doesn't say anything about the sequences

[spring plume]

not sure what u mean by this
but it's not limit, n is infinity here(growing infinity)

[errant otter]

you don't "multiply by infinity"

that's... simply nonsensical. What would such a notion even mean? It's like asking what infty/infty or infty - infty is

[spring plume]

why not
i m multiplying both sides by same infinity(n) which simply cancels out. inf/inf and inf-inf is not valid when both infinites are different . but n/n and n-n is valid since they are same.

[brittle root]

that's not how it works

[loud maple]

'infinity' is not something that a real number can be multiplied by, the way you have done it here

[brittle root]

recall the definition of a limit

[spring plume]

i wonder why not? isn't 5* inf =inf?

[errant otter]

how do you define what kinda "infinity" you're dealing with here, and how do you "show" that they're the "same" infinity which "cancels out"?

[patent acorn]

what's "inf"? and what does it mean to multiply by it?

[spring plume]

it should be growing infinity that is n
and it's n which is same here

[errant otter]

what is a "growing infinity" ._.

[spring plume]

i mean which doesn't have an end
other type would be to have an end but u can't reach it
they are same anyways i guess

[spring plume]

infinity

[patent acorn]

what's "infinity"?

[spring plume]

bruh

[errant otter]

exactly

that's how bruh your question is too, since infinity literally is just "bruh" when you talk of it like that

[spring plume]

so thats it i m just saying 0.99... is tending to 1 and can be considered 1 in our world but it should be kept in mind that it is not exactly 1

[errant otter]

it is exactly 1

[patent acorn]

"0.999..." is exactly 1

[errant otter]

so first things first

how do we define a number to be equal to another

does the definition "there's no other number in between them (loosely speaking)" fit well with u?

[spring plume]

it could be any method u choose

[errant otter]

if u wanna be rigorous abt it

[spring plume]

by area or algebra

[errant otter]

we don't consider "area" here

we're just dealing with scalars

numbers

not area

[spring plume]

it can be proven by area as well bro
just like u prove 1/2 + 1/4 + 1/8 ... = 2

[errant otter]

that's geometric arguments

[patent acorn]

(wait what does it even mean for a number to tend to another number?)

[errant otter]

but you can do it from other viewpoints

[spring plume]

like imaging going inside number line from the left to 1
u keep on going smaller and smaller (near to 1 ) but are never able to reach exactly 1.

[loud maple]

This isn't rigorous

[patent acorn]

going smaller and smaller
and what does it mean for a number to do this?

[spring plume]

its obvious since there are always infinte numbers between 2 real numbers in number line

[errant otter]

2 numbers $x$ and $y$ are considered to be equal each other if $\forall z > 0$, $|x - y| < z$ How abt this?

[sterile pumice]

Kiameimon | Welt Rene (glomed)

[spring plume]

yeah and how does it apply to 0.99... and 1

[errant otter]

well then if we can show that no matter what z you pick 1 - 0.999.... is less than z

we are done

which... well, how abt we write 0.999 as $\lim_{n \to \infty} 1 - \frac{1}{10^n}$

[sterile pumice]

Kiameimon | Welt Rene (glomed)

[spring plume]

true but ... i didn't find anything rigorous

[errant otter]

ok well bee probably has a more intuitive argument time to run

[patent acorn]

well i have a different argument, idk if it's any more intuitive

[errant otter]

so tldr, let's slap that in!
$|1 - \lim_{n \to \infty} 1 - \frac{1}{10^n}| < z$
Do you see why this is true?
When we fix some value for z, then we can always "adjust" the value of $n$ to show that it's always less than $z$

[sterile pumice]

Kiameimon | Welt Rene (glomed)

[spring plume]

if u choose 1-0.99... will be less than z (z belonging to real number )
then next u pick z to be 1-0.99... and 1-0.99.. to be less than that and well it keeps going..

[errant otter]

yes

exactly

[patent acorn]

...actually it doesn't really keep going
if you claim that 1-0.999... is less than itself then you've created a contradiction

[spring plume]

but well this doesn't stop does it?

[errant otter]

another perhaps more intuitive way is to say "there's no number in between 0.999.. and 1"
Which you can see is obv true, since well, how could there be a number x such that 0.99... < x < 1?

[spring plume]

well we taking z to be 1-0.99..

[errant otter]

well how abt htis instead

n = 2/z

wait

oops

[patent acorn]

1/(1-z)

[errant otter]

lemme edit that

[patent acorn]

...actually can i ask
what is 0.999...? how are you defining it?

[spring plume]

bruh u asking now

[errant otter]

well 2 ways u can define 0.99...

[patent acorn]

(i was trying to ask them not you, i already know how you're going to define it)

[errant otter]

[normal heart]

there should be a channel for questions like these...

[errant otter]

I'd believe this works? Let's see
say $z = 10^{-5}$ , so $n = 2*10^5$
so $|1- (1-\frac{1}{10^{2 \cdot 10^5}})| = 10^{-2 \cdot 10^5} < 10^{-5}$

ez

[sterile pumice]

Kiameimon | Welt Rene (glomed)

[shell minnow]

Not considered

It is

The symbol 0.9999… = sum from 1 to infinity 9/10^n which is exactly 1

[grizzled rapids]

Indeed. An "I think I know better than mathematicians and rigorous proofs because there is no way my intuition about ambiguously defined concepts can be wrong" channel would be most welcome. Then we can isolate inane "discussions" like this from channels like #elementary-number-theory.

Questions like this from people who have no intention of being educated, and simply want to be told they are right, should not be entertained. What a waste of all your time.

[wooden glen]

Just redirect that discussion to #math-discussion when it crops up -- but do try to be polite about it; name-calling is not going to achieve anything of value.

[spring plume]

wtf is your problem i never said I am right
this is just to discuss and increase your knowledge
i would be much happy if i can get a definite proof of this

people like you who follow every-thing they see blindly have no worth.
so stfu if you have no answer to my question

[spring plume]

also this is convincing indeed.

[open mist]

As per the definition of a number by its decimal expansion, we have

$x = 0.9999\dots = \sum_{n=1}^{\infty} 9 \times 10^{-n} = 9 \times 10^{-1} \sum_{n=0}^{\infty} 10^{-n} = 0.9 \frac{1}{1-\frac{1}{10}} = 0.9 \times \frac{1}{\frac{9}{10}} = \frac{9}{10} \frac{10}{9} = 1$

No debate to be had

[sterile pumice]

Bezier doubt

[torn escarp]

this doesn't explain anything, you've just pushed the question about these infinitely many digits rewritten into this infinite sum but haven't explained how you get that answer, so it's not much better than saying .999... = 1 unfortunately.

[torn escarp]

I like this answer

[open mist]

This does assume you know the definition of the object you're talking about yes

[torn escarp]

yeah, you can't assume they know the thing you're explaining to them

[open mist]

One is intuitive. One is for math majors

[torn escarp]

to get on the roof of a house:
start on top of the roof

[open mist]

I saw that they already did all the intuitive stuff

He asked for a "definite proof", so I gave him

[torn escarp]

it's not

[open mist]

Obviously you can't do anything properly in math if you haven't defined things. So ofc I'm going to give a proof that uses the damn definition

[torn escarp]

the question is about an infinite sum from the get-go and not understanding how that can be equivalent to 1 because they lack an understanding of distance. Rewriting the already infinite sum in sigma notation to do your algebraic manipulation x=.999... = .9 + .099... = .9 + x/10 doesn't really fill this gap.

but I understand why this is appealing

at least we would want it to be consistent with algebra like this

[wooden glen]

Usually when people get hung up about 0.999... it's because they don't know that notation is supposed to mean a certain infinite sum. (Often they just have a vague assumption that the decimal expansion is what a real number really is). Repairing that confusion is a matter of getting them to understand that 0.999... means such-and-such limit -- after that point, actually evaluating the limit is a short and easy step.

[spring plume]

yes true
the question would be about infinity and not 0-999.. and 1.

[spring plume]

well lets just close this with this

[spring plume]

but i would like to know what I did wrong here.

[torn escarp]

first thing that doesn't make sense to me that you've written is:

(n-1)/n =n/n (n=inf) (or 0.99.. =1)

[spring plume]

why not?
isn't 1/n (n->inf)->0?
that would make it 0.9999 and so on as n tends to infinity

[patent acorn]

it is indeed true that the limit as n goes to infinity of 1/n is 0

"goes to" is doing a lot of work here
what this statement actually means is that for any positive distance ε, there is some (finite) number such that if n is bigger than that number, the distance between 1/n and 0 is less than ε

saying that n is equal to infinity is not valid, "infinity" in this context isn't really an actual thing and even if it was it's not something you can do arithmetic on

also, your conclusion, that 0.999... is "tending to" 1, doesn't make sense
the sequence 0.9, 0.99, 0.999, 0.9999, ..., does tend to 1, but "0.999..." doesn't mean that sequence, it means the limit of that sequence, which is 1

[grizzled rapids]

If saying I understand something because I can prove it rigorously makes me blind, then I do not want to imagine what you consider "seeing". I do not have an original answer for your question, because it was already answered about 20 times before I chimed in. I will say I am glad to see you seem to have a more open mind now. Maybe this definitely-not-#elementary-number-theory discussion can finally come to an end, after 9.9999... separate proofs of why 0.999...=1.

[spring plume]

yes exactly i m saying the limit of the sequence is 1

[patent acorn]

and that means 0.999..., which is defined to be the limit of that sequence, is exactly equal to 1

[spring plume]

hmm yes

[verbal cedar]

@spring plume i remember struggling with this question many years ago and watching this video.
https://youtu.be/TINfzxSnnIE

it basically summarizes all the arguments outlined above

ignore the video that may show up in the recommended she uploaded called "Why Every Proof that .999... = 1 is Wrong", it's an april fools video 😆

[analog raptor]

Proof by induction. Let p be fixed, and we will do induction by n. Let (n_p) denote the binomial coefficient n over p, and [n_p] the floor.

1. Induction base: n=p+1 easily checks out.
2. Induction hypothesis: Let the statement be true for some n>p.
3. Induction step: Let us prove the statement for n+1.
   3.1 p does not divide n+1: We want to prove: (n+1_p) = [n+1_p] = [n_p] (mod p). We have (n+1_p)(n-p+1) = (n_p) (n+1) = n_p (mod p) from which we can deduce what we wanted to prove.
   3.2 p divides n+1: Then n=kp-1. We want to prove (n+1_p) = [n+1_p] = [n_p]+1 (mod p). We have (n+1_p) = (n_p)((n+1)/(n-p+1)) = n_p (mod p). But we also have [n_p] = [kp-1_p] = k-1 and plugging that back in the previous modular equation we get (n+1_p) = k = [n_p] + 1 (mod p) which we wanted to proof.
   So, for a fixed p we proved that every n satisfies the problem, so we can just move the p along all of the prime numbers, therefore, proving the problem for all prime p, and natural numbers n.

I wanted to verify my proof since I found a different proof in my book that I got the problem from. Thanks in advance.

[spring plume]

thanks

[gilded breach]

@patent acorn Following our conversation before, I was able to prove the converse of Euclid's Lemma

[white lion]

a question on the pedagogy of modular arithmetic, every time I've been taught it we begin with the definition that a is congruent to b modulo m iff m | (a-b). From what I've read this notation invented by Gauss was used to in practice to denote if two integers had the same remainder or not, which is really the core of modular arithmetic, remainders, however this fact is proved only later as Theorem. The typical definition is very confusing at first and I see no reason why we cannot instead use the much more insighful definition that a is congruent to b modulo m if they share the same remainders and then prove the fact that a is congruent to b modulo m then a-b is a multiple of m, which is a useful property in proving facts about modulo m, why isn't this the case?

[verbal cedar]

this would probably be a better question for #math-pedagogy
but generally I agree. I think it's more intuitive to say
a=b mod m iff a=qm+r and b=km+r for 0≤r<m and integers q,k

[white lion]

Will do, thanks.

[turbid topaz]

Show that the addition with rational numbers like this is well defined. How does one do that?

[timber bone]

Show that the sum is independent of the choice of representative.

[turbid topaz]

I don't quite get it.
I tried: a/b=a'/b' and c/d=c'/d' so that a*b'=a'b and cd'= c'*d. Now I tried adding but don't quite get how this does the work

[solid garden]

You need to show that if a/b = a'/b' and c/d = c'/d', then a/b + c/d = a'/b' + c'/d'

You basically do it by expanding all the definitions

I recommend starting from the end and working back to the beginning to try to calculate everything out and then pick a new piece of paper and start writing the proof from the beginning to the end in the proper order

[somber dirge]

hello! - ive got a hw assignment on numbers, mostly just covering sets of numbers, powers and index laws, logarithms, arithmetic sequences and geometric sequences - i was just wondering if anyone had the spare time to explain a couple things to me in more detail? (:

[slim dew]

am i crazy?

[dusty dragon]

how did you get 3780?

If x = 3780, then x = 2^2 * 3^3 * 5 * 7 in which case, what would your y be?

(note that there’s no possible way you can obtain a y that satisfies both gcd and lcm, think about why)

[slim dew]

i thought that because the lcm has all the prime factors of both x and y, if i multiplied the gcd by the smallest prime factor then i'd end up with the smallest x that isn't the gcd (idk if this is right)

but okay so xy = lcm(x,y) * gcd(x,y), y = lcm(x,y) * gcd(x,y) / 3780 = 560290500

[dusty dragon]

You’re half right, the lcm does contain all of the prime factors. Suppose that we just multiply the gcd by 2; what must the power of 2 in y be?

Here, the power of 2 in x is now 2