elementary-number-theory

[rapid plover]

And I'm lost again

(This is the only bit of elementary nt I've done ever)

[stiff rivet]

there is really multiple things you can do then

if p divides a, then p^n divides a^n

and this gives you trouble with p = a^n / b^n

you need a small extra thing though

[rapid plover]

I did not consider the implication p^n divides a^n

[stiff rivet]

and that is here

when writing a rational number as a/b, you can further choose a, b in such a way that gcd(a, b) = 1

so then if p divides a, it cannot also divide b

and you have multiple ways to bring this to a contradiction

[rapid plover]

Tbh I think these analysis course notes presuppose some familiarity with nt

Which is the main issue here

I'm just in deep waters

Of unfamiliarity and inexperience

[stiff rivet]

as the name suggests, those are elementary things, you can learn them in not too much time

seems the main thing you should watch out for is only apply divisibility results if everything involved is an integer

[rapid plover]

Mhm

[stiff rivet]

so like in this case the first step is to turn everything into an equation involving integers and arrive at something like pb^n = a^n

[rapid plover]

I'll find some short nt course notes to help with results like fta and generalised euclids lemma which are coming up soon here

[rapid plover]

That's reasonable in hindsight haha

Thanks for the help Loch

[stiff rivet]

at this point one could already use gcd(a, b) = 1 and conclude b = 1 (using for example the fundamental theorem of arithmetic)

and then p = a^n is ofc a contradiction for n > 1

[rapid plover]

I haven't formally seen gcd or fta yet

It's literally 10 pages on

[stiff rivet]

hm

i think you need the notion of gcd for this

or well, coprime integers

[rapid plover]

That's why I thought it was assumed

I found some lecture notes

So much math to learn but so little time

[compact moth]

My friend told me that any integer can be written on the form:

2^n × 3^m + m, is this true?

[still flare]

I'm pretty sure you can't write 6 in that form.

[compact moth]

True

What about either

2^n × 3^m + m
Or
2^n × 3^(m-1) + m?

[still flare]

I'm really not interested in working through every single one of your suggestions, so if you're going to continue, please provide something like a proof for us to check. Fwiw, you still cannot express 6 in either of those forms provided m,n are integers.

[jolly robin]

Hey, I have a little question regarding the euclidean algorithm.
I dont understand why gcd(a,b)=gcd(r0,r1)

i understand how to apply the algorithm just not prove it lol

[leaden swan]

gcd(x,y)=gcd(x,y-kx). Try proving that you will understand that step better

[jolly robin]

there was a lemma that said that gdc(a,b)=gdc(a,b+an) but i dont understand how that translate to the induction hypothesis

the GDC between two numbers is the same as consecutive remainders?

[leaden swan]

Substitute x=a,y=b ,k=q

Call y-kx as r1 and x as r0

And you get your base step

[jolly robin]

[leaden swan]

Well if you know that lemma it's just juggling symbols

[jolly robin]

i dont understand the consecutive remainder thing

with j and j+1

how do those have the same GDC as a and b

[leaden swan]

You got the base case right?

[jolly robin]

yeah

[leaden swan]

So by induction hypothesis,you have gcd(a,b) = gcd(r_i-1,r_i) for some i(well base case is i=1)

Note $\gcd(r_{i-1},r_{i})=\gcd(r_{i},r_{i-1}- r_{i} q_{i+1})=\gcd(r_{i},r_{i+1})$

[sterile pumice]

Drake

[leaden swan]

And $\gcd(r_{i},r_{i+1})=\gcd(r_{i-1},r_{i})=\gcd(a,b)$

[sterile pumice]

Drake

[jolly robin]

ok im gonna take a break and come back

[jolly robin]

Does that work because for some i the rest will be eventually 0?

[leaden swan]

Well no that works because
$\gcd(r_{i-1},r_{i})=\gcd(a,b)$ by induction hypothesis

[sterile pumice]

Drake

[jolly robin]

Ok but r is the remainder when what is divided by what?

Thats what I dont understand

[jolly robin]

ok i understand finally

it works in a recursive way if i understand correctly

[leaden swan]

Yes

[jolly robin]

yay

now i gotta show this but i wont even attempt it until tmrw since i currently ahve no idea

[gilded tinsel]

euclidean algorithm it

oh thats what uve been doing

[jolly robin]

How tho, I dont know the remainder and quotient I get

Or which is bigger for that matter of fact

[primal pewter]

denote that expression by f(m,n) and try to express it in terms of f of something "smaller" by using the fact that gcd(a,b)=gcd(a,a-b)

you can find some sort of recurrence which is very similar to the Euclidean Algorithm

to be more precise, gcd can be described recursively as a function g that satisfies this:
if a>=b, g(a,b)=g(a-b,b)
if a<b, g(a,b)=g(a,b-a)
and of course g(x,x)=x
Try to prove something like this for f.

[jolly robin]

you mean the left side or right side?

in the video he says its a trick regarding dividing polynomials

i might honestly just give up and move on in order to not waste that much time on it\

[jolly robin]

i found a solution on math exchange

i understand it and can recreate it, but I wish I could just come up with this stuff by myself

[primal pewter]

left

[jolly robin]

i managed it at last\

so if you divide a^m-1 by a^n-1 you will get a^r-1

and the exponents transform like gcd(n,m)=gcd(r,m)=...

[rapid plover]

In this proof of the division algorithm - Given $a,b \in \mathbb{Z}, b \neq -0. \exists ! q,r \in \mathbb{Z}$ such that $ a = qb+r$ and $0 \leq r < b$ I don't understand how we can deduce that $0 \leq r < b$? obviously it makes sense from my intuition but don't understand how we achieve it here

[sterile pumice]

swifteeee

[stiff rivet]

both bounds follow from the definition of q; the lower directly by definition and the upper you can show by contradiction

[rapid plover]

Suppose $r \geq b$. Then $a = qb + r = qb + bc$ for some $c \geq 1$ then, $a = b(q + c)$ which contradicts that $q = max{qb \leq a}$

[sterile pumice]

swifteeee

[rapid plover]

I have a feeling that somethings missing here

[stiff rivet]

this doesnt work

you can just show that in this case q+1 is in {q : qb <= a}

[stiff rivet]

this seems to use the statement of the theorem in the proof and also a is not necessarily divisible by b

[rapid plover]

mhm

I'll send a fuller screenshot of the notes, because I don't see how they make the implication, maybe that would be easier to explain

well I have the intuition, I just cant prove it true

[stiff rivet]

its a bunch of annoying algebra

if r >= b, then b-r <= 0

now (q+1)b = qb + b

rewrite qb in terms of a and r via the definition of r

and arrive at (q+1)b <= a

this contradicts the maximality of q

[rapid plover]

makes a ton of sense

thanks loch 🙂

[sacred junco]

https://gyazo.com/201623ddda028f878de415d6c1840dc9

how does [7] = [2] ?

[stiff rivet]

again, refer to the definition

$$7\equiv 2 \pmod{5}$$

[sterile pumice]

Lochverstärker

[sacred junco]

where do u get the mod 5 from?

[stiff rivet]

from the Z_5

[sacred junco]

oh

the z_n is the mod n

?

[stiff rivet]

yes, its stated in the definition

[jolly robin]

In the video series Im watching its given as gcd(a,b)=gcd(a+bn)

[primal pewter]

yes, I just took n=-1

[jolly robin]

I saw that I just wanted to know if it applied for any integer

Thanks

[odd atlas]

It's a cryptography text, and based on theorems so far, I cannot seem to reason about how it can be permutation

Googling, I found a fact on Wikipedia which says that it is a reduced set of residues, which I agree with

But I still wonder if it's also a permutation?

[west glade]

if you reduce the elements of that set mod N, you get R back, just in a different "order"

[odd atlas]

Ah yeah, now that I think about it....

Thanks!

The new reduces elements will all be unique by the previous result

So makes sense yeap

Actually.. I am still wondering, why is it not possible for there to be an a such that we get some element that should not be in reduced set

I mean, they said a = 1,2,... N - 1

No

they also have gcd(a,N) = 1

Quite a weird way to put that

Nevermind

[jolly robin]

What learning resource are you using?

[fathom loom]

is this just proving the quadratic formula?

but I guess you have to make sure the solutions are viable given mod N right..

how do you do that?

[stiff rivet]

the gcd and quadratic residue condition ensure that the things exist

so you just have to show that they actually are solutions

at least for 1.

[fathom loom]

how come?

like it ensures the solutions exist?

[stiff rivet]

it ensures that you can divide by 2a by bezouts lemma and that you can take squareroots by definition of quadratic residue

[fathom loom]

oh interesting

okay

I didn't realize I needed those to be able to confirm that I can do that

so first we divide by a and we know we can do that bc of bezouts?

then we get rid of the constant value, c/a, and add (b/2a)^2 to both sides which ig we can do bc of quadratic residue def?

finally after completing the square you take the square root which you know you can do because of quad res and you get the quadratic formula?

[gilded tinsel]

the derivation is exactly the same

u just dont know whether the numbers you need necessarily exist

the conditions tho, gurantee they do

[stiff rivet]

you dont have to do anything of this, you just have to plug in the x given into the quadratic equation and verify its a root

for 1. at least

2. is harder

[upper nacelle]

6.0+2=8 😎

[fathom loom]

ah okay, thats true.. silly mistake

[fathom loom]

why do i need quadratic residue to justify taking squareroots? and same question goes for dividing by 2a

[gilded tinsel]

suppose a is a quadratic residue. Then there is some b such that a=b^2. So in a sense, root(a)=b. If there were no such b i.e. a was not a quadratic residue then taking the suare root wouldnt make any intuitive sense. root(a) would not be an element of the integers mod N. Youd be scratching ur head as to how to define that

[primal pewter]

for the second question: division is defined as multiplication by the inverse; so you need 2a to be invertible modulo N in order to be able to divide by 2a;
now 2a invertible modulo N is equivalent to gcd(2a,N)=1

I think working through the exercise 2 would help you understand better these steps
in exercise 1 you only have to prove those expressions are indeed solutions (after, of course, justifying they are well defined)
in exercise 2 you have to derive them; while doing this, it should become clear what conditions should be imposed and especially why

[fathom loom]

Okay I understand this thank you so much!

[fathom loom]

Thank you this makes sense! I'll try working through 2. appreciate your help guys

[minor nexus]

Hey! How do I prove that if gcd(a,b)=1, then a! divides (b+1)(b+2)...(b+(a-1))?

[still flare]

Interesting problem.

[sacred junco]

a divides b+i for some i in {1, ..., a-1}.

[latent hare]

can you explain further how that helps?

[sacred junco]

Same thing works for a-1.

[still flare]

Not quite

It's insufficient to show merely that 1, 2, ..., a divides the product

[sacred junco]

Yeah actually this needs some fixing

[still flare]

as for instance, it is true that 2, 3 and 4 divide 12, but 12 is not divisible by 4!.

[sacred junco]

Yeah, I thought that every factor of a! will divide exactly one of the product.

[still flare]

Exactly one? No I don't think so

[sacred junco]

Yeah, thats why I used 'thought':D

[still flare]

We need to use that gcd(a,b) = 1 somewhere, but I haven't a clue how

[sacred junco]

but writing a=kb+r should work

r non zero

[still flare]

Right, maybe we can use strong induction on r?

Eh maybe not actually

[latent hare]

ok

the claim is identical to showing $(a+b) \mid \binom{a+b}{a}$

[sterile pumice]

peaceGiant

[latent hare]

according to the following link: https://math.stackexchange.com/questions/1165229/how-can-we-prove-that-a-binomial-coefficient-n-choose-mis-divisible-by-the-rat
we have the following beauty

$\frac{\gcd (a, b)}{a+b} \binom{a+b}{a} \in \mathbb{N}$

[sterile pumice]

peaceGiant

[still flare]

Ew...

[latent hare]

...👀

agree to disagree

[umbral bridge]

cmon, it's the application of your favorite lemma :D

/j

[still flare]

Am I the Bézout guy now

Have I tied myself to that result

;_;

It is a really nice lemma tbh

[umbral bridge]

definitely super helpful

half of the questions in elem. number theory books that have gcd(a, b) = ... use it one way or another

[sacred junco]

Would like some help with this lemma:
Suppose a is a primitive root mod n
Prove there can't exist a primitive root b mod n that does not come from the set ( 1, a^1, a^2,... a^(phi(n)-1) )

[primal pewter]

Since a is a primitive root, 1, a, a^2,..., a^(phi(n)-1) are precisely all the units in Z/nZ. Now b, as a primitive root, must be a unit.

[sacred junco]

I have a problem that is "if n is an integer greater than 1 and (n-1)! =1 mod n, prove that n is prime". I saw the answer to it so I don't need help with the answer, but I am confused because isn't 1 mod n always 1

[still flare]

You're confusing mod for an operation. It is not something that you put things in and get things out of, it is a relationship between numbers.

When people say that a = b (mod n), they mean that a and b differ by a multiple of n.

So when people say that (n-1)! = 1 (mod n), they're saying that (n-1)! = kn + 1 for some whole number k.

Usually people use ≡ instead of = in these things, to emphasise that this is not the usual equality relationship.

[sacred junco]

oh ok thanks

i was mega confused

[still flare]

It is surprising to me that you're being asked to do this question, but you haven't covered the definition of equivalence modulo n. I think if you're doing a course or reading a book, you should go back and check the definition that was given.

[sacred junco]

ah Wilson's theorem

a nasty one

[still flare]

How is it nasty lol

Very nice theorem actually.

Not the most helpful, mind you

[sacred junco]

wilsons theorem has a negative 1 involved

so its not that

[still flare]

Yes unfortunately Avina, your problem statement is incorrect lol

It should be -1, not 1 on the end.

I did not notice that tbh

[sacred junco]

im pretty sure both are true

[still flare]

No.

[sacred junco]

i hope both are true bc i have a proof which makes sense to me

saying x ≡ 0 mod n is equivalent to saying kx = n right

[still flare]

That's true.

It is technically correct that (n-1)! = 1 mod n implies that n is prime

but it also implies that n=2 :)

So it's not particularly helpful.

[sacred junco]

yeah i was like

wait doesn't n just equal 2

this can't be right

but theres the equivalent thing

[still flare]

If you would like us to check your proof, you're welcome to post it here.

[sacred junco]

does ab! =a!b!?

probably not

definitely not

[still flare]

No.

[sacred junco]

i dont know if i should replace the = with a ≡

if it is = it is so trivial that i feel like it shouldnt be on the homework

[still flare]

I'm a bit frustrated because I just explained this

[still flare]

See here.

I think it's abundantly clear that they mean equivalence mod n.

[sacred junco]

we might've tbh

i left my notebook at home but I have that book

but damn ok

[umbral bridge]

You put the k on the opposite side

nk = x

[stoic crypt]

Just had a friend ask me a coding question about number theory and I have no idea how to start

Given a, n, r, need to find smallest m such that (a * m) % n = r, and we testing all m from 0 to n will take too long

[leaden swan]

Can't you just find a^-1 mod n and multiply that with r?
If a, and n are not co-prime,divide a,n and r by gcd(a,n) and do the above procedure

@stoic crypt

This will be a log(n) solution which is probably acceptable

[signal cedar]

can anyone help?

[gilded tinsel]

im not sure which theorems you know but id suggest considering $\sum_{n\leq x}\left[\frac{x}{n}\right]\Lambda(n)$

[sterile pumice]

rockpaperscissors

[signal cedar]

yea but that gives extra factors at n=p^2

or p powers > 1 in general

[gilded tinsel]

ok

take the first power

and seperate it from the rest

the higher powers will give your error term

adn the 1st power is just the sum ur trying to find an asymptotic for

[signal cedar]

yea I know that

I still don't know how to compute the sum

i.e. which summation formula would help me

[gilded tinsel]

which part do you not know how to cmpute?

the error term

or the sum of the von mangoldt function?

[signal cedar]

both actually

summation formulas help if we have a function which is differentiable

[gilded tinsel]

do you know how to turn sums of arithmetic functions weighted with floor functions into a double summation over divisors of n?

[signal cedar]

no

[gilded tinsel]

what kind of summation formulas do u know

[signal cedar]

abel, euler-maclaurin and dirichlet hyperbola

[gilded tinsel]

r u using any textbook?

[signal cedar]

apostol

[gilded tinsel]

apostol has a proof of this if i recall

[signal cedar]

ohh

can you tell me where

its theorem 3.11

i think

ahh then its easy the total sum turns out to be xlogx + O(x) and the error term turns out to be 1/2x^{1/2} log x +O(x^1/2)

which seems right!

thanks @gilded tinsel

[sacred junco]

How are the max/min values chosen for x, y, z?

[lone pumice]

Is the question to find all coprime a,b with LCM 360 and GCD 12?

[fervent crest]

How do you find coprime integers with gcd 12

[lone pumice]

That is a good point

Idk what I was thinking

[lone pumice]

Ok so I'll go through one of them and the rest are similar

Because LCM has a factor of 2^3, both x and x' need to be at most 3 (or the LCM would have a higher power of 2 as a factor), and one of them equal to 3 (or it would be smaller one), so the max is 3

[sacred junco]

@lone pumice What about the min?

From the 12, right?

[lone pumice]

Same idea with the GCD, at least 2 or it would be larger, ...

[sacred junco]

Also, what's the difference b/w ordered and unordered pair?

[lone pumice]

For an ordered pair (2,3) is not the same as (3,2)

For an unordered pair they are the same thing

I think the usual notation is just {2,3} for example but then I'm not sure what to do when the pair is something like {1, 1}

[sacred junco]

yeah it's just this that was confusing me: @lone pumice

[sacred junco]

Why is the first paragraph true?

[sacred junco]

if a_0 and b_0 have a common factor n, then a and b would each be divisible by dn. since d is the greatest common divisor of a and b, this forces n = 1

I understand that step, I just don't get why it suffices to show that lcm = da_0b_0 for the pf to be complete

what is this a proof of

gcd(a,b) lcm(a,b) = ab

just multiply them lol

gcd is d and if lcm is da_0b_0 what do you get

(remember a = da_0 and b = db_0)

I get that part..

What I'm asking is...ok, so where does the intuition come from for lcm(a,b) = da_0b_0?

Basically I see how proving that gives the equality but I don't see where it came from intuitively...

[gilded tinsel]

lcm(a,b) is obviously divisible by a and b and hence da0 and db0

naively, you can make a number thats divisible by both by just multiplying them together

i.e. (da0)(db0)

but then u ask whether this really is the lcm?

or are we multiplying by extra factors?

well when we take the product (da0)(db0) we get two factors of d

but we know that d already divides both a and b

so we dont need another factor of d

thats how i see the intuition anyway

[sacred junco]

here is the question.

my question is how do i go about proving it since, using induction i won't be able to prove it.

[west glade]

which of these

and why does induction not prove it

[sacred junco]

if you use induction, 1 needs to be in the set but 1 is not greater than 1 and the and the condition x>y>z won't hold since, 2>1>1 is not true.

[latent hare]

(for n > 1)

[sacred junco]

how do i go about proving it?

[rapid plover]

termwise maybe

2 > 1, 4 > 3, 5 > 6 etc

n > n-1 forall n > 1

[latent hare]

yea, or if you insist on induction, apply induction on the hint as is

[rapid plover]

am I okay to ask my question now tarun?

[sacred junco]

for now, please do.

[rapid plover]

Here, in this section, we are looking at finding general solutions to recurrence relations (defined at the top of the page). I understand how the two solutions r_1^n and r_2^n come about, I'm just confused how we get to "A little thought shows that if r_1^n and r^n_2 are both solutions to the recurrence (with any initial conditions) then so is C_1r_1^n + C_2r_2^n for any constants C_1 and C_2". What is the thought that gets us to this place?

[latent hare]

have you tried plugging that expression in the recursion $$x_{n+2} - bx_{n+1} - cx_n = 0?$$

[sterile pumice]

peaceGiant

[latent hare]

btw it's the same recursion, just moved everything to the left because I think it's nicer when you plug in the values

Try first plugging C_1 r_1^n to convince yourself that the constant just multiplies the original recursion, while then try plugging the sum, since you'll get the sum of the two separate recursions for r_1 and r_2

[rapid plover]

$C_1r_1^{n+2} - bC_1r_1^{n+1} - cC_1r_1^n = 0$

[sterile pumice]

swifteeee

[rapid plover]

$C_1(r_1^{n+2} - br_1^{n+1} - cr_1^n) = 0$

[sterile pumice]

swifteeee

[latent hare]

yup, as you can see, the thing in the brackets is itself zero, which solves the recursion

[rapid plover]

a root of the recursion lol

[rapid plover]

$(C_1r_1^{n+2} + C_2r_2^{n+2}) - (bC_1r_1^{n+1} + bC_2r_2^{n+1}) - (cC_1r_1^n + cC_2r_2^n) = 0$

im not really sure what we've achieved here

[latent hare]

first bracket second term should be C_2

after that fix, factor all terms with C_1 in one set of brackets, and then all terms with C_2 in a second set of brackets

[sterile pumice]

swifteeee

[rapid plover]

$C_1(r_1^{n+2} - br_1^{n+1} - cr_1^n) + C_2(r_2^{n+2} - br_2^{n+1} - cr_2^n) = 0$

[sterile pumice]

swifteeee

[latent hare]

great, since all brackets are again zero, that linear sum of the roots of the recursion is itself a solution

[rapid plover]

how does this relate to our definition of a two-term recursion given before? (what does each C, r etc. mean in the factorised form given above)

[latent hare]

having difficulty understanding the q tbh ¯_(ツ)_/¯

or rather difficulty providing a useful answer, so someone else can answer that

[rapid plover]

i think for now i'll have to accept that the general solution to the recursion is infact the general solution to the recursion on faith and move on

[latent hare]

oooor be patient till someone more knowledgeable shows up :D

all I know is the general solution can be represented as a linear combination of any two particular solutions to the recursion, the solution set in my mind is basically a line, and to discover the set of all points on that line (all solutions) you need at least two points (two particular solutions)

[rapid plover]

makes sense

[rapid plover]

lols

[sacred junco]

Working through some exercises rn, stuck on (d) and (e), can someone explain how to approach?

[still flare]

Think about the prime factors involved for (d).

For (e), good luck.

[little holly]

Can someone help me prove the second statement using euclid's algorithm ?

[brisk skiff]

you reading it for comp math?

[dark zealot]

why if a|b and a|c then a|bu+vc

i understand that if a|b then b contains all of the prime numbers contained in a, and same for c
but i dont see how addition and subtraction preserves that

[stiff rivet]

what is your definition of |?

[dark zealot]

divides

[stiff rivet]

yes, i want the precise definition

[dark zealot]

b=qa

with q in Z

[stiff rivet]

ok then apply this twice

bu + vc = aqu +vaq'

and now you have to rewrite this in the form aq'' for some q''

this is just algebra

[dark zealot]

So the common prime numbers are preserved by linear combination?

also here for example

a=bq+r

and the symbol is for smallest common divisor

I dont understand the intuition behind this

My main weakness in arithmetic is seeing how addition and subtraction relates to division and multiples because i can easily understand how to decompose numbers in prime terms, and thus division and multiplication and biggest common divisor and the smallest common multiple are just a play on the prime decomposition, but in subtraction i have no idea what's happening to the prime numbers involved so i lose track

[stiff rivet]

Z-linear, yes

[dark zealot]

Z-linear?

[stiff rivet]

coefficients in Z

its not true with real or rational coefficients

[dark zealot]

okay, so when i add or substract 2 numbers, the common prime numbers will stay in the result

[stiff rivet]

yes, by factoring

[dark zealot]

I rly didnt see that before, thats cool

[dark zealot]

Well this is obvious then

because r still contains all common divisors

incredible thank you so much

[dark zealot]

wdym by factoring tho? any linear combination will contain the common factors right??

[stiff rivet]

any Z-linear combination of a and b will contain the factors that are shared by a and b

[dark zealot]

great

tysm

[stiff rivet]

thats the gcd

so gcd(a, b) divides xa + by for any integers x, y

[dark zealot]

Yeah thats a result i knew but somehow i didnt get until now. Its very powerful

Its weird how i can see results like that written in mathematical terms and not understand what it truly means, but thinking that i do

[stiff rivet]

you have to play with it a bunch

[dark zealot]

And is there something equivalent for smalles common multiple btw?

On how linear combinations affect it

ig not

[stiff rivet]

no

you can translate gcd statements into lcm statements and vide versa by using gcd(a, b)*lcm(a, b) = ab

[dark zealot]

so this would be mean that there is a k such that kn is a multiple of the gcd of a,b

the congruence relation in general

[dark zealot]

.

[stiff rivet]

hm? i also cant parse the image

[sacred junco]

can someone help me in this one? it says "2022" was writen "n" times, what is the value of n to "2022...2022" be divisible by 23?
answer: ||11|| but i have no idea how can i do this

[wooden glen]

The long number is the sum of a finite geometric series: 2022 + 2022·10000¹ + 2022·10000² + .... + 2022·1000^(n-1).

Use the formula for a geometric series to get a closed expression for this. It involves a division by 9999, but 9999 is coprime to 23, so you can consider this expression modulo 23, and a bit of algebra will then show you're looking for an n such that 10000^n == 1 (mod 23).

That is, just the order of the congruence class of 10000 in the multiplicative group modulo 23.

This group has order 22, so there is only one of the options given that can be the order of an element (according to Lagrange's theorem).

[sacred junco]

🛐 thx!!

[fathom loom]

yo no way this is just p = 2q-1 => phi(2q) right?

[fathom loom]

s = 260921763, does anyone know how to do this?

N is a composite number, with prime factors 16111 and 16319, so I know I can split the problem into mod those two numbers

I believe Euler's totient theorem can be used to reduce the exponent? im not sure how or why, but then you'd also have to prove that you're allowed to use it which I'm not sure how to do either

any help please?

[grizzled escarp]

How should I approach this?

[stiff rivet]

your idea is correct, why dont you just do it?

use chinese remainder theorem, to reduce it to the prime(power) case

then you can reduce the base mod your prime p and reduce the power mod phi(p)

you can prove this for example by applying euclidean division to the exponent

[fathom loom]

How do you use chinese remainder theorem here I'm sorry I need to brush up on my algebra, do you set it as a system of congruences?

and then the rest is done by the theorem?

I guess the two exponents are throwing me off, I'm not sure how to approach that

[low plaza]

So im pretty new to number theory

Can someone give me a road map to this question

Beyond just use modular arithmetic

Ive been struggling on this for awhile

[wooden glen]

No idea, sorry. (But note that they must mean no positive integer solutions; there are plenty of solutions where either x or y is 0).

There's a proof at https://planetmath.org/exampleoffermatslasttheorem but it doesn't really align with your hint.

[fathom loom]

does anyone know how to show this? is it just as simple as
p = 2q-1
=> phi(2q)

[fathom loom]

can you show me how to do that?

[inner anchor]

You can still simplify phi(2q) by the multiplicativity of phi

But yes thats most of the solution

[fathom loom]

wow

p = 2q-1
p-1 = 2q
=> phi(2q)

[stiff rivet]

i dont know if i have a low tech explanation, the high-tech explanation is if N=pq with p, q coprime, then there is a ring isomorphism Z/NZ -> Z/pZ xZ/qZ, that maps x mod N to (x mod p, x mod q)

[fathom loom]

oh boy

ok hold on

[stiff rivet]

so its enough to compute thing in Z/pZ xZ/qZ,

and then move back

you can also try working directly with mod N, you can still reduce the exponent modulo phi(N) and the base modulo N

i dont know if this suffices for this problem though

[fathom loom]

ok I get this I think, this is saying i can simplify into having my two equations each with mod (coprime factor of N)

but its reducing the exponent that im confused about

[stiff rivet]

essentially

can you be more specific?

[fathom loom]

Yes ok so

we have a third exponent right

213456789^987654321^s

that s idk what to do with

[stiff rivet]

oh yeah

the exponent is 987654321^s

[fathom loom]

lol

that makes sense actually

jfc

[stiff rivet]

i mean this then turns into computing a small representative of 987654321^s mod phi(N) (or mod phi(p), mod phi(q) respectively)

and you can apply the same thing again if that helps

(i kind of assume everything simplifies at some step and the answer will not depend on s)

[fathom loom]

is there anything special about using 987654321? what if it was s^s^s?

[stiff rivet]

i assume its a number that will simplify nicely

[fathom loom]

I see

[stiff rivet]

and is big to look hard

[fathom loom]

not depend on s eh

interesting

[fathom loom]

wait wdym here

[stiff rivet]

actually probably N is the one chosen such that it simplifies nicely

[fathom loom]

I think so

because earlier in this question we computed that

[stiff rivet]

you know eulers theorem, right?

[fathom loom]

im trying to relearn it rn :'))

but basically we found that for N's prime factors, we have 4 possibilities for the residues of s could be

if thats any use

[stiff rivet]

hm, can you share that?

[fathom loom]

yeah sure

so N is 262915409, with prime factors 16111 and 16319

calculating this you find that the 4 possibilities for what the residues of s could be are {(1, 1),(1, -1),(-1, 1),(-1, -1)}

and funny enough -1 and 3 cover all of these cases because together these two vectors span this space

basically -1 has (-1/16111) = -1 and (-1/16319) = -1, and 3 has (3/16111) = -1 and (3/16319) = 1, so we can treat them as the vectors (-1, -1) and (-1, 1) in (Z_2)^2

so does eulers phi function take as input an integer, and outputs number relatively prime to n?

[stiff rivet]

what i mean is eulers theorem tells you that $a^{\varphi(N)} \equiv 1 \pmod{N}$, so if you want to compute say $a^b \pmod{N}$ for some $b > \varphi(N)$ you can use $$a^b = a^{\varphi(N)+ (b-\varphi(N))} = a^{\varphi(N)}a^{b-\varphi(N)} \equiv a^{b-\varphi(N)} \pmod{N}$$
to get a smaller exponent; if it is still big, you can use this more often to make the exponent as small as possible

[sterile pumice]

Lochverstärker

[fathom loom]

ooh I see

[stiff rivet]

the euler phi function phi(n) gives you the number of elemts in {1, ..., n} that are coprime to n

[fathom loom]

so b is 987654321^s here, and its clearly bigger than phi N

[stiff rivet]

i think its best if you review eulers theorem, its important

[fathom loom]

since phi N is 16111 or 16319

[stiff rivet]

yes

[stiff rivet]

no

[fathom loom]

yeah no tahts wrong

lol

[stiff rivet]

(i also dont think your other exercise is related to this)

[fathom loom]

oh damn, too bad

[fathom loom]

so then do I just know its bigger than phi(N) by computation?

or is there a more obvious tell

I found that phi(N) is 262882980

[stiff rivet]

well, still seems big

if you use the chinese remainder theorem first, you can instead use phi of your primes

[fathom loom]

oh obviously

right

so get phi of 16111 and 16319 right?

[stiff rivet]

sure

though you should know those two immediately

[fathom loom]

right

-1 lol

thank you so much! I'll try to see where this takes me

[stiff rivet]

previous exercise makes it seem like you know s though?

[fathom loom]

why is it the case that prime -1 is coprime..?

yes I know s, sorry I thought I wrote that

its 260921763

[stiff rivet]

well, all numbers smaller than p are coprime to p

because you know, p is prime

[fathom loom]

oh

duh

wtf

[stiff rivet]

the only numbers not coprime to a prime p are p, 2p, 3p, ...

[fathom loom]

right that makes sense simply by definition

im still getting used to the terms again

sorry

[stiff rivet]

but yeah you can use this reduction theorem again

then you have to compute phi(phi(p))

and reduce s that way

and then you get a result at some point

[fathom loom]

wait wdym

so you have the two congruences with the factors of N

and you reduce once

then you reduce again?

or

i mean I guess you already reduced once

wait no im misunderstanding this I think

we have $123456789^{987654321^s} \mod 16111$
, clearly $b > \varphi(N)$ bc
$$987654321^s > \varphi(16111)$$

so we now can try to find $$123456789^{(987654321^s) - \varphi(16111)} \mod 16111$$

[sterile pumice]

Delta Syndrome

[fathom loom]

that has to be wrong..

[stiff rivet]

why?

[fathom loom]

oh it isn't??

just seems like (987654321^s) - \varphi(16111) is not like.. super fun

[stiff rivet]

its just not general enough to be useful

[fathom loom]

right

[stiff rivet]

as i said, you can reduce the exponent mod varphi(p)

you should try proving that

so something like:

if $b \equiv c \pmod{\varphi(n)}$, then $a^b \equiv a^c \pmod{n}$

[sterile pumice]

Lochverstärker

[fathom loom]

ah so bc we have the antecedent

so like

err

987654321^s \equiv something mod 16111

wait

[stiff rivet]

i dont think you understand the statement

its very general, and you should probably try to understand that first

this is what lets you reduce the size of exponents in congruences

[fathom loom]

alright thank you I'll try to figure that out

wait this is just eulers theorem

[stiff rivet]

is it?

its an application, yes

[fathom loom]

yeah I think I see that

I'm confused somehow about what you mean when you say reduce the exponent mod varphi(p)

like I don't see what that is pointing to

for some reason

perhaps I need a break

like take 987654321^s, and reduce it, and take mod phi(n)?

[stiff rivet]

there are infinitely many numbers congruent to a mod n

one of them is smallest

reduction is finding the smallest

this will make those calculations easier

[fathom loom]

I see

what do you mean by the exponent exactly? sorry

is it (987654321^s)?

[stiff rivet]

yes

but you can compute 987654321^s = ? mod phi(n)

and you can apply the same theorem again

(you can also reduce the base, which you will have to do as well)

[fathom loom]

is ? 1688^5

[stiff rivet]

depends on the n you are considering

i was trying to avoid having to do any calculations myself while trying to help you

[fathom loom]

xD

fair

im considering 16111

[stiff rivet]

whats s again

[fathom loom]

sorroy sorry

wait i think i got this

thank u so much

ill lyk

s is 260921763

[stiff rivet]

you can always check on wolframalpha

,w 987654321^260921763 mod phi(16111)

[sterile pumice]

Results provided by WolframAlpha

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

Requested by Lochverstärker#5585

[stiff rivet]

,w 1688^5 mod phi(16111)

[sterile pumice]

Results provided by WolframAlpha

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

Requested by Lochverstärker#5585

[stiff rivet]

so doesnt seems to check out

but wolframalpha can compute the final solution and every intermediate step you want to make, if you want to check

[fathom loom]

actually I got stuck

so

I took 123456789 mod 16111

then

mod the exponent

[stiff rivet]

this should be the first step, yes

careful that you have to mod the base and the exponent by different numbers though

[fathom loom]

um

so now

987654321 mod 16110

actually no

i take the prime factors

of 16110

which are 2, 3, 3, 5, 179

and check 987654321 ^s mod each one

if i have a zero

which i do

at 3

i continue from that

so now i have 14307^0^s = 1

nvm that was wrong

this is it

[fathom loom]

nvm I still don't know how to do this

[mystic walrus]

can someone explain to me how this work was done?

[brittle root]

On first observation I would notice that 3x+4y added to 7x+5y would be 10x+9y

Helpfully we can just add 3x+4y again

The rest of the proof follows

[brittle root]

Mostly came from playing around with it I'm guessing

Another interesting observation is that 3, 4 are coprime so you can produce any integer

In fact you can find integers s and t such that 3s+4t=1 (corollary, since gcd is a linear combination)

Observe too that 7 and 5 are coprime so again you can find integers

[brittle root]

We can take this and multiply it by 13b where b is some integer

We now have $3(s \cdot 13b) + 4(t \cdot 13b) = 13b$

[sterile pumice]

DerpZ

[brittle root]

Setting x = 13bs and y = 13bt

[fathom loom]

wdym by most?

[cerulean rivet]

I am not convinced that this set, which is not denoted to be finite, is also bounded below, especially not by 0.

Given that this set literally just comes with element of the form a-ib for natural i, what stops me from just continuing the set?

Like lmao isn't saying that this set is bounded below like assuming the very thing we're trying to prove

(my primary confusion is that this set is not denoted to be finite, I can just select a-nb for some sufficiently large n and wooooah we're below 0!!!!)

[daring barn]

you seem to be correct

it is not a priori bounded at all except above by a lol

[brittle root]

which book is this?

[cerulean rivet]

https://www.isinj.com/mt-usamo/Elementary Number Theory - Underwood Dudley (2008).pdf

[brittle root]

Yeah I'm not convinced either

I think gallian's abstract algebra book explained it better

The ... notation is pretty poor tbh

[cerulean rivet]

man I hate number theory books

[brittle root]

Maybe something like $S = { a - nb \mid a-nb \geq 0 }$

[cerulean rivet]

trying to learn from something small that doesn't assume algebra

[sterile pumice]

DerpZ

[cerulean rivet]

and this was like the first decent book

[cerulean rivet]

lmao could be

[brittle root]

also obviously n is an integer

I think you have to apply the WoP

[cerulean rivet]

huh

[brittle root]

well ordering principle

but they didn't restrict the set bounds??

[cerulean rivet]

hhqh

haha*

Ig man bruhhh

[brittle root]

perhaps this explanation is more satisfying

sorry for small text

[cerulean rivet]

no worries bruh

thanks bros im gonna clock out for the night 💀

[lilac elk]

you can prove with q1 and r1, q2 and r2 and conclude que both q and both r must be equal

[brittle root]

Are you talking about the uniqueness portion of the proof?

[mystic sinew]

@brittle root is this susanne epp textbook ?

[brittle root]

gallian contemporary abstract algebra

[dark zealot]

x=2[19] and x=3[15], find x

x=3[15] then x=3[3] and x=3[5] by the chinese theorem

then what?

how to solve this set of equations

[west glade]

Chinese remainder theorem is constructive

Or you could just guess some numbers

Check all small numbers that are 2 mod 19 whether they are 3 mod 15. You'll have to check at most 15 numbers

[dark zealot]

wdym

i dont want to guess

[west glade]

Well then use the construction from CRT

15 and 19 are coprime so you can apply it

[dark zealot]

how?

i still dont really understand it

the theorem

is there some good video or source?

to gain the intuition

i just learned it a few minutes ago in my algebra class when we reached the fact that Zmn is isomorphic to Zm*Zn

if m,n are coprime

[west glade]

Well I assume you proved the CRT?

Follow the proof but now with the specific numbers 15 and 19

Well I assume you did a constructive proof.

If not then the internet definitely has resources on that

[low plaza]

Hi guys i dont know how to do 5

I know the method for diophantine equations with two variables

But i cant find a way to do this even online

[wooden glen]

Hmm, one (somewhat unsystematic) approach would be to solve 12x_1+21x_2+15x_4 == 0 (mod 9) and then compute x_3 to make the overall equality come out right.

[supple palm]

that seems like the right approach to me

it simplifies further to 3(x_1 + x_2) + 6x_4 = 0 mod 9 from which you can proceed simply

[wooden glen]

Perhaps divide the entire equation by 3 as the very first step to make the numbers smaller, though.

[blazing lance]

Does anyone know what this notation means?

What is nZ?

is it Z/nZ?

[wooden glen]

$n\bZ = { na \mid a \in \bZ }$

[sterile pumice]

Troposphere

[blazing lance]

oh lol thanks

why cant I just do m=ab, so mz={abn | n\in Z}?

Oh nvm I see

theres common factors maybe

So something like this?

[wooden glen]

That's a rather verbose way to define the least common multiple, so yes.
It's also just ab/gcd(a,b).

[vernal void]

prove that 11 divides 456^654 + 123^321

using F.L.T

• not sure where to begin 😮

[wooden glen]

("FLT" will usually be uderstood as "Fermat's Last Theorem" -- you want Fermat's little theorem, which unfortunately has the same initials).

First, you can write what you want to prove as $456^{654} + 123^{321} \equiv 0 \pmod{11}$.

[sterile pumice]

Troposphere

[vernal void]

haha

[wooden glen]

What is the exact statement of the Fermat's little theorem you know?

[vernal void]

i believe so Tropo

p prime, a int. --> a^p-1 = 1 mod p

[blazing lance]

[wooden glen]

This version needs an additional assumption that a is not a multiple of p.

Luckily, neither 456 nor 123 are multiples of 11.

Now, even before you start using Fermat, you ought to know that $a^b \equiv (a\bmod n)^b \pmod n$, so you can start by using that to simplify your goal.

[sterile pumice]

Troposphere

[vernal void]

oh right

p does not divide at

a

@wooden glen

Can U explain this step to me?

I don't understand the congruency

how can we break down that into

4-5+6, for example

what gives!

❤️

[wooden glen]

It's using that 10 == -1 (mod 11) and therefore 100 == 1 (mod 11).

Personally I'd find it quicker to say:

456 = 440 + 16 = 440 + 11 + 5 == 5 (mod 11)
123 = 110 + 13 == 110 + 11 + 2 == 2 (mod 11)
(which is just long division, forgetting about the quotient, but can still be done in your head).
But both methods work.

[clever trout]

Can someone help me with this question?
i don't know if regular induction works

i'll send wat i have tried so far

d ≥ 2 so
d -3 ≥ -1

but i'm trying to show that

p_k+3 -3k -3 is > 0

so i'm kinda stuck here

any idea wat number theory for primes is needed?

pls ping me if u reply thank yu

[wooden glen]

Long induction seems more promising, tbh.

Then you can go from n-2 to n, using that at most two of any six successive numbers can be prime. (Other than 2 or 3, but they are never p_(n+2) anyway).

@clever trout

[summer ocean]

what is tranistive property???

it say x=1

a=x

what is a

help guyss

[blazing lance]

https://www.google.com/search?q=transitive+property&client=firefox-b-1-d&sxsrf=ALiCzsbB4lSPotz9L8Gz8sPLy039Vangiw%3A1664398051860&ei=47I0Y_mMNLag5NoPm46TwAM&ved=0ahUKEwi5ipX1rbj6AhU2EFkFHRvHBDgQ4dUDCA0&uact=5&oq=transitive+property&gs_lcp=Cgdnd3Mtd2l6EAMyBAgjECcyCwgAEIAEELEDEIMBMgsIABCABBCxAxCDATIFCAAQgAQyBQgAEIAEMgUIABCABDIFCAAQgAQyBQgAEIAEMgUIABCABDIFCAAQgAQ6CggAEEcQ1gQQsAM6BggAEB4QFjoICAAQHhAPEBY6BQgAEIYDSgQIQRgASgQIRhgAUPEBWJgLYPcMaAFwAXgAgAFHiAHfBZIBAjEzmAEAoAEByAEIwAEB&sclient=gws-wiz

[fathom loom]

is p-1 mod p always -1?

[west glade]

yes

[fathom loom]

true

[tender cedar]

Let $f(x), g(x)$ be two polynomials without common factors (except constants). Show that $f(x) + yg(x)$ is irreducible

[sterile pumice]

sam

[tender cedar]

This seems trivial, but I'm slightly unsure how to interpret the y here

It's getting too late I think my brain is fried

The lecture notes are rly quite unfinished so it didnt give us much tools or discussion before these excercises

[sterile pumice]

sam

[tender cedar]

Another excercise, Let $f(x)$ be a polynomial. Show that $y^2 + f(x)$ is reducible iff $f(x) = -g(x)^2$ for some polynomial $g$, seems equally trivial if you just know how to interpret it

[sterile pumice]

sam

[clever trout]

is this strong induction?

[wooden glen]

Yes, "long induction" and "strong induction" are two names for the same variation.

[primal pewter]

@clever trout the trick is that the equality does not hold
so if you have p_(k+2) >= 3k, you actually have p_(k+2)>=3k+1
use this idea in the induction step

[clever trout]

hi filip what do u mean by equality?

[wooden glen]

(It's not clear to me how the +1 would make things easier, FWIW).

[clever trout]

p_(k+2) >= 3k,
and since d >=2 ,

p_(k+3) >= p_(K+2) + 2 = 3k + 2

err

so i got 3k+2

just need 1 more

[primal pewter]

p_(k+2) can't be equal to 3k, because it would be divisible by 3 and so it won't be a prime

[clever trout]

oh ok

OH

[primal pewter]

so p_(k+2) is at least 3k+1

[wooden glen]

Ah!

[clever trout]

OHHH

DAMN SON

wow

damn

alright

ok so p_(k+2) >= 3k+1

p_(k+3)
= p_(k+2) + d

= 3k + 1 + d

and since d >= 2

p(k+3)

= 3k + 1 + 2
= 3k + 3

omy god we are done

@wooden glen @primal pewter thank you two for your time gentlemen

https://tenor.com/view/thank-you-bow-michael-scott-the-office-gif-18616386

https://tenor.com/view/youre-welcome-pleasure-keanu-reeves-its-a-pleasure-thank-you-gif-18395277

[fathom loom]

does anyone know how to use CRT to find all the square roots of some y mod N?

my N is 260924709, I know I can split it into 16111 16319 which are the prime factors of N

but I don't know how to continue from here

please im on my last straw im losing it 🥲

[wooden glen]

It's not exactly a complete method, but if you can find square roots modulo the prime factors separately, then the CRT allows you to combine them into a square root modulo N.

You then still need a way to find a square root modulo each prime factor.

[fathom loom]

yeah

I just figured another thing out

[wooden glen]

By the way, the prime factorization of 260924709 is 3 · 86974903, not sue where you got 1611 and 16319.

[fathom loom]

oh oops

wait I must've gotten N wrong

262915409

yeah my bad

sorry

[fathom loom]

that's N

[wooden glen]

So the first factor is 16111 not 1611 :-)

[fathom loom]

correct..

did I actually type that?

what the hell

[wooden glen]

Hmm, no you didn't.

[fathom loom]

oh nevermind then

but yeah

16111 and 16319

so I just found an algorithm we have to calculate square roots but

[wooden glen]

Dont know what me miss one of the ones.

[fathom loom]

I'm not sure its sufficient

this was a previous exercise we proved

and 16111 mod 4 is 3

so we know that y^16112/4 is 7064 mod 16111

so those are the corresponding square roots of the primes I think

like if we do the same thing for 16319

but yeah

I don't know how to continue

I know you're supposed to find the inverses so like

16111^-1 mod 16319 and similarly 16319^-1 mod 16111

but I don't know why

I think there might be a special version of CRT for primes

[fathom loom]

any ideas?

[wooden glen]

I can never remember how it goes exactly. The CRT itself just says that a solution exists (and is unique), but if you dig up a proof of it, is should be constructive enough to tell you how to proceed.

[fathom loom]

I haven't been able to figure it out by myself I've looked around on the internet everywhere

that's too bad then

[fathom loom]

wait this is not true, its not 7064

[wooden glen]

Not immediately.

The CRT is something like if you can find x and y such that
x==1 (mod p) y==0 (mod p)
x==0 (mod q) y== 1 (mod q)
then ax+by == a (mod p) and ax+by == b (mod q).
But x==0 (mod q) says that x is a multiple of q, and finding the inverse of q mod p tells you which multiple of q it has to be to make x==1 (mod p).
Similarly (but opposite) for y.

[fathom loom]

oh so that's why you want the inverses

so its cong to 1

oh ok ok

== is congruent right?

[wooden glen]

Yes, common ASCII approximation for $\equiv$.

[sterile pumice]

Troposphere

[fathom loom]

ok ok ty

can you explain what this is saying?

I can't even realize how this result was reached

then I should be done ;-;

turns out its correct..

and the screenshot is a typo.. nevermind

[hardy basin]

Hi, why is q < sqrt (n /p)?

[primal pewter]

I think it should have been q <= sqrt(n/p).
They used the fact that any composite number has a prime factor less or equal to its square root.

To prove this, let's say we have a composite number n; so we can find a,b>1 integers such that n=ab. Clearly, we can't have a>sqrt(n) and b>sqrt(n) in the same time, so at least one of these is false. Let's say the first one is false, so a<=sqrt(n). Now pick any prime divisor of a, and we are done.

[heady sequoia]

hi

[noble obsidian]

any tips?

Prove that if f(x) is a polynomial of degree 3 with integral coefficients (that is, f(x)=a_3x^3+a_2x^2+a_1x+a_0 and a_0,a_1,a_2,a_3∈Z) and none of the integers f(0),f(1),f(2) is divisible by 3, then f(x) does not have a root in Z.

[west glade]

if f(x) has a integer root k, then f(k)=0 mod 3

[noble obsidian]

is contradiction my best option here?

[west glade]

well depends on what you mean by "best". but it certainly is an option

[noble obsidian]

my easiest option

[west glade]

probably

[noble obsidian]

lets say I don't know much about congruences. Can I just plug in 3q + r for every x value?

[west glade]

yes

[knotty oriole]

How would I go about checking uniqueness of a solution for ax + by = n?, Given integers a,b and solving for integers x,y?

[still flare]

Think about the shape of the solution set for fixed, nonzero a,b.

This will help you form a plan of attack

[knotty oriole]

Thanks

I got that there's an infinite solution if there's a solution or none

[still flare]

I agree with you!

[shut scaffold]

I haven't taken a math class in a while, and I know I am butchering this (a limit in analysis). I hope I just need a couple pokes in the right direction (or a suggestion of a better channel to ask in). https://mathb.in/72940

[upper gale]

try to multiple on the top and bottom by:

sqrt(n^{2} + n) + n

and you should be able to find the result ^^

[shut scaffold]

Thank you! Is this going in the right direction so far? https://mathb.in/72941

[upper gale]

huuuuh, last line is wrong

[shut scaffold]

Bah, I can only do that on top. Gotcha, thanks again!

[knotty oriole]

Do you have an intuitive explanation? I have a proof on the paper but it doesn't make much sense to me

Intuitively some line describing x and y shouldn't necessarily have infinite integer points

[still flare]

Because it’s a line with a rational slope

[knotty oriole]

Ah

[still flare]

If I go along enough, eventually I get another integer pair. Donezo

[knotty oriole]

Fair, thank you

[random path]

hello guys, I have two questions about this exercise:

1. I thought about a solution where the sets have the property to be multiple of a prime number, so I would have A1 = {2,4,6,8,...} A2 = {3,6,9,12,...} A3 = {5,10,15,20,...}. Is it acceptable as solution?
2. I don't understand the proposed solution, can someone give me some references? Thanks

[west glade]

well in your case you have for example that 6 is both in A1 and in A2

which is not allowed

so you need to be more careful

what they mean is to take A1 = {1,3,6,10,15, ...} and A2 = {2,5,9,14, ...} etc, that is Ai = {i'th row}

or equivalently column

[leaden swan]

Well consider this:
Let f be a bijection from N x N to N.

Now Let B_i={(i,n) | n \in N}. Then the sets f(B_i) will partition N.

I think this is what they are trying to do

Each B_i can be thought of as a "row" of NxN

[random path]

thank you both

[stone urchin]

number 2 please

brother?

opp sorry wrong chennel

[analog onyx]

can anyone help me write 1 as a linear combination of 34 and 55

i have used the euclidian algorithm to get to the gcd and back substituted but im struggling to reduce it in terms of 34s and 55s

oh wait its just gonna be the two previous fibonacci numbers isnt it

[tropic yarrow]

I think so in the end

or something like that

F(n)*F(n+2) - F(n+1)^2 = +-1

[pearl gyro]

how can I get to n | (n-2)! from here?

[night quail]

let a,b>2, n=ab. show a,b<ab-2. then (ab-2)! must have a and b as factors. thus ab | (ab-2)! -> n | (n-2)!

[pearl gyro]

Thank you!

I have this so far, but I've been struggling on how to show 2a < a^2 - 2 for n>2...

[night quail]

@pearl gyro where do you use the argument that 2a < a^2 - 2

regardless, let a=3. then clearly 2*3 < 9-2
now let a>3. then
a^2 - a < a^2 - 2
and a-1 > 2
so a^2 - a = a(a - 1) > a * 2

so a^2 - 2 > 2a for a > 2

[radiant gust]

Guys im having trouble understanding this homework assignment, if someone has the time to help me understand it and perhaps solve it

For each of the following subsets of ℤ, explain whether the subset is well-ordered or not (by the usual ordering on ℤ).
i) even numbers
ii) perfect squares
iii) the integers that are strictly greater than -5

[still flare]

Explain what you don't understand; nobody can read your mind, nor does anyone want to simply give you the answers.

[pearl gyro]

To (hopefully) show a and 2a are two distinct integers between 3 and n-2 and show that a^2 | (n-2)!

[pearl gyro]

thank you so much🥹

[night quail]

np

[signal ice]

Hi.

[brisk belfry]

i know its a strange question, but how can i find the minimum and the maximum of 4 numbers.
an expression for minimum of 2 numbers is: (a+b-|a-b|)/2, and for maximum: (a+b+|a-b|)/2. So i need such a formula for 4 numbers

[stiff rivet]

just look at the numbers lol

you can also use min(a, b, c) = min(min(a, b), c)

and proceed by induction, then use what you have

[brisk belfry]

theyre random

[brisk belfry]

so min(a,b,c,d) = min(min(a,b), min(b,c), min(c,d)) = min(min(min(a,b), min(b,c)), min(c,d)))?

[latent hare]

You can use the expression you already have. Say the numbers are a, b, c, d.
S1 = (a+b-|a-b|)/2, S2 = (c+d-|c-d|)/2 and the overall minimum is (S1+S2-|S1-S2|)/2

I don't see though how this would be faster than just looking at the numbers, rather comparing them

[stiff rivet]

this works but its a bit too complex

you can just always compare with the next number

min(min(min(a, b), c), d)

[brisk belfry]

ah, ok

[stiff rivet]

you can find the min of n numbers by finding n-1 mins of two numbers

if the numbers are "random" (you probably mean arbitrary?) this adds nothing to the math though

you can just write min(a, b, c, d) in place of the min everywhere

and nothing changes

[latent hare]

WLOG let a<=b<=c<=d :D

[brisk belfry]

yes, but then i need to find the min of other three, then min of remaining two

so basically i need to rearrange them from smallest to biggest

[stiff rivet]

you dont

[stiff rivet]

plug in min(a, b) into your formula

[brisk belfry]

?

[stiff rivet]

then plug the result and c into your formula again

and then that result and d into your formula again

you get some giant algebraic expression in a, b, c, d

then you can simplify this in some sense

[brisk belfry]

ok, thats what i need

thank you

[stiff rivet]

technically the expression is algebraic in a, b, c, d and some absolute values that appear

the same works for max

its just a much writing down and algebraic simplification at the end

[knotty oriole]

does anyone's library have access to the following:
A.M. Vaidya. An inequality for Euler's totient function. Math. Student 35 (1967), 79-80.?

it's in the mathematics student 1967. the journal is impossible to find (even on the less legal sites) and my library only has from 2012

[analog onyx]

thoughts on this?

[torn escarp]

what kind of thoughts are you looking for, is this a proof you wrote and are having doubts about?

[analog onyx]

yeah just asking for a second set of eyes for correctness

not so sure about the last sentence of the second paragraph

[torn escarp]

I'm about to go to sleep, someone else might help, but you might want to say what [2] is

[analog onyx]

i changed it to n | (x1 - x2) bc i think that x1 congruent x2 mod n shows they just differ by n and arent neccessarily unique

its bezouts identity, okay

[wind glacier]

What's the best method to solve this??

[wooden glen]

Hmm, my first thought would be to look for triples whose product isn't a multiple of both 5 and 4, which feels like it should be doable by inclusion-exclusion.

[wind glacier]

i tried to make cases but it is going too lengthy ....can you pls elaborate

[wooden glen]

Triples where 5 doesn't divide the product are those where none of the numbers are 5 or 10.

Triples where 4 doesn't divide the product are those where all numbers are odd, plus triples with one number being 2, 6, 10 and the two others being odd.

Triples where neither 5 nor 4 divides the product are those where all numbers are odd but not 5, plus ones with one number being 2 or 6 and the two other odd-but-not-5.

[wind glacier]

im trying again..thanks

[cedar dragon]

Hello, new here, but I was wondering... how to solve this?

First step was just taking a number, 48, and finding all factors ( 1,2,3,4,6,8,12,16,24,48)

And then taking the prime factorization of all of those

Getting 2^20 * 3^5

So now Im thinking, is there any way to create the same product using a different set of prime numbers?

[wooden glen]

One place to start might be that if the original n is not a perfect square, then P_n is always a power of n, since the divisors come in pairs.

(And if n is a square, then P_n is a power of its square root).

[cloud nova]

i wish i could

wait im thinking

i cant help

but look >>>> some energy for you to complete it

good luck!!!

✨ ✨

[buoyant mason]

I'd take a look at p^(k-1) for prime p

[cyan fox]

hey

i need help with this: q,p>3 are primes, show that 24 divides p^2 - q^2

[south oar]

A hint is that this statement holds as long as p,q are both odd and not multiples of 3

First write p^2-q^2=(p+q)(p-q). Then notice if both p,q are odd then p+q and p-q are already both even, so it's already divisible by 4. Then you see p and q are congruent to either 1 or 3, then for each case see what p+q and p-q will be modulo 4. Lastly p and q are congruent to either 1 or 2 modulo 3, and again for each case see what p+q and p-q will be modulo 3.

[cyan fox]

Thank you

i found a pretty cool solution tho

primes can always be written as 6k +- 1

so i can just say p=6k+1 and q = 6k -1

so with factorization i just get 24k / 24

[sour rivet]

Is there a way to write 0.01001000100001000001..... as a repeated fraction?

[south oar]

Well no you can't say that, but you can still do all the cases and realized that the product is 24 times something

What if you were given p=7 and q=13 then both are 6k+1, and if you're given 5 and 11 then both are 6k-1

It's pretty similar to what I told you to do, but this is a bit cleaner

[torn escarp]

no because it's not a repeating fraction, but you can write it in summation notation, it'll end up something like (just roughly guessing it's something similar to this, since you're basically adding consecutive numbers, not gonna work it out) $$\sum_{n=2}^\infty \frac{1}{10^{\frac{n(n+1)}{2}+n}}$$

[sterile pumice]

Merosity

[sour rivet]

To be clear I know it's irrational and can't be written as a fraction, but was looking for a way to write it as a repeated fraction kind of like how sqrt2 can be written as 1/(2+1/(2+1/2+...

Is this what you answered?

Makes sense, because I wouldn't even know how to start expressing it 🙂

Now realizing the word I was looking for was "continued fraction"

[south oar]

Well, every real number can be written as a continued fraction

But it's just the numbers won't be really nice for this number

Because if the numbers are periodic then the number must be a root of a quadratic equation with rational coefficients