elementary-number-theory

[abstract flax]

That is true. For some reason I was thinking that at least 2 of the ai's had to be coprime, but that's not true

I don't see how the lemma is helpful at all if you can't show anything is coprime though

[wise oyster]

same

except that it proves the theorem for the case n = 2

[abstract flax]

Yes

@wise oyster Okay, I think I have a proof for you

[wise oyster]

im all ears

[abstract flax]

Suppose the statement is true for n = k. We prove it for n = k+1.
If gcd(a1, ..., ak) = 1, then every sufficiently large integer can be written as a linear combination of a1 to ak and we just add a zero coefficient to a(k+1).

[wise oyster]

the a1,a2,a3,...,ak arent necessarily the same as those of the n = k+1 case

[abstract flax]

Wut?

[wise oyster]

we're proving a statement about a certain size not about specific numbers

like

we can assume that the gcd of k coefficients is 1

but when we consider the k+1 case those arent necessarly the same coefficients

[abstract flax]

Yes, so we have proven it for every list of size k. Now we take an arbitrary list of size k+1, and say if the first k are comprime we can use the n=k result.

[wise oyster]

and gcd(a1,a2,a3,...,ak+1) = 1 does not necessarily mean that gcd(a1,a2,...,ak) = 1

[abstract flax]

I know, that's why I said if. The if not part is coming

[wise oyster]

oh sorry

ill let you finish

[abstract flax]

If gcd is not 1, let d be the gcd. Then d and a(k+1) must be coprime, since any common divisor would divide all of the ai. Then we apply the lemma, so sufficiently large integers must be a linear combination of d and a(k+1), but d is a linear combination of a1 to ak so we can sub that in.

The end.

[wise oyster]

ahhhh

that makes sense

[abstract flax]

I still don't understand theirs lol

[wise oyster]

i think theirs does the same thing

but badly explained

[abstract flax]

Very badly, haha

Suppose every thing we want to be true is true. Then everything works well. Q.E.D.

[wise oyster]

thanks a lot

it's not a very complex proof if you think about it but i had trouble wraping my head around the frobenisu number and the gcd at the same time

kept mixing them up

[abstract flax]

That makes sense. Np. I haven't seen you around in a while. I don't known if that's because I am less active or because you are.

[wise oyster]

i wasnt active for a while cause i was pretty sick and couldnt do shit

[abstract flax]

:( glad you're better. Good luck with maffs.

[wise oyster]

otherwise for a bit i hung around #multivariable-calculus whenever id be reading up on diff eqs

thanks

[abstract flax]

@wise oyster I think you don't even need induction

Let d = gcd(a1, a2,..., a(n-1)). Then gcd(d, an) = 1. So there exists N such that for M > N, M = xd + ay for some x and y. Since d is a linear combination of a1 to a(n-1), we are done. This seems like a complete proof.

[abstract flax]

@wise oyster oh noooo

I've led you astray

d as a linear combination of a1 to a(n-1) can have negative integers

[wise oyster]

oh yeah shit

well thanks anyways

maybe ill give it more thought tomorrow

[regal aspen]

I feel like this can be solved using mod

[wise oyster]

Ah i wake up, get on, and see lunasong typing

[abstract flax]

Lol

Suppose the statement is true for $n=k$, and show it is true for $n = k+1$. Let $d = \gcd (a_1, \dots, a_k)$, then $\gcd(\frac{a_1}{d}, \dots, \frac{a_k}{d}) = 1$. So there exists $N$ such that every $M > N$ can be written as a linear combination of $\frac{a_1}{d}, \dots, \frac{a_k}{d}$ with nonnegative integers. Choose a prime greater than N which does not divide $a_{k+1}$, say P, then $dP$ is a linear combination of $a_1, \dots, a_k$ with nonnegative integers.

Now $\gcd(dP, a_{k+1}) = 1$, so we apply the lemma to find an $N_0$ and we can sub in dP as a linear combination of the $a_1, \dots, a_k$ with nonnegative integers.

[sterile pumice]

Lunasong

[abstract flax]

@wise oyster I hope that works, but I might realize why it doesn't again in 10 minutes

gcd(dP, a(k+1)) is 1 because gcd(d, a(k+1)) is 1 and gcd (P, a(k+1)) is 1

[wise oyster]

Yeah

I had tried a proof using the division by gcd but i hadnt thought about the prime step

Thing is

Wait no

[abstract flax]

I figured you just needed something that is coprime with a(k+1).

[wise oyster]

I personally cant see anything wrong with the proof but couldnt see anything wrong with the last one either at first

Thanks

I gtg to my MRI now ill be back in a few hours

[abstract flax]

Np, at least here therr are definitely only nonnegative coefficients

Bye

[wise oyster]

Thought more about it and still cant find any flaws

[abstract flax]

Yay

[wise oyster]

there's likely a nicer proof we can come up with though, namely in replacing P with some better bounded number so that we can glean more information on how large the frobenius number is. Cause this proof works but taking a prime p that doesnt divide ak+1 can allow for a number likely much larger than necessary

so that problem boils down to, can we find a nice expression for j such that gcd(g(a1,a2,...,ak) + j, ak+1) = 1

or at least some bounds for j

[sacred junco]

how we can prove there are no solutions in Z, with modular arithmetic, n^3-3^m=2022

mod 9?

i tried

Cubes can either be 0, 1 or -1 mod 9

thanks!

[sacred junco]

(try that out yourself)

It should be smooth from here

[sacred junco]

Can there be intuition given behind why for every integer $n$ we have $n^2 \equiv (a - n)^2 \pmod{a}$

[sterile pumice]

LINEAR_ALGEBRA_GUY

[sacred junco]

Intuitive reasoning for why it is true, not just a proof?

[sage fern]

the proof is very intuitive

(a - n)^2 = a^2 - 2an + n^2, that's just clearly going to be equal to n^2 mod a

we could try difference of two squares

(a - n)^2 - n^2 = ((a-n) + n)((a-n) - n) = a(a - 2n) == 0 mod a

that's kinda pretty

[torn escarp]

start from -n = a-n mod a, then square both sides

[sacred junco]

(2m+3)(3m+4) = 35^n, solve in positive integers.
i think only m=n=1 is a solution in positive integers but i dont know how to prove

[broken igloo]

consider the gcd between the 2 factors...

[sacred junco]

how?

gcd[(2m+3),(3m+4)]=1

[broken igloo]

so...?

[sacred junco]

..?

[lusty hornet]

gcd( 2m+3, 3m+4) = gcd( 2m+3, m+1) = gcd( m+2, m+1) =1

[broken igloo]

so... what happens next? This highly constrains 2m+3 in terms of n

[lusty hornet]

firstly if a solution exists, m must be odd, it cannot be even

[broken igloo]

what else?

[lusty hornet]

it was actually @sacred junco 's question

[broken igloo]

hmm, oh, sorry

Remember you need to factor 35^n into two coprime factors...

[sacred junco]

thank you !

[stiff estuary]

why tho

$2n7=14n$

[sterile pumice]

galois

[stiff estuary]

what is the proof for $14n\neq2^m ; \forall n,m \in \mathbb{N}$

[sterile pumice]

galois

[sage fern]

7 does not divide 2^m

[stiff estuary]

is this an axiom or can you explain it more?

[sage fern]

well just consider the prime factors

[stiff estuary]

2 and 7

and 2

oh ok

I get it

[sage fern]

ok

[stiff estuary]

wow I can't believe I missed that

time to start over with the basics

[sage fern]

so it goes

[stiff estuary]

$ \begin{array}{c c c c}
&\mathrm{E}&\mathrm{I}&\mathrm{N}\
&\mathrm{E}&\mathrm{I}&\mathrm{N}\
&\mathrm{E}&\mathrm{I}&\mathrm{N}\
+&\mathrm{E}&\mathrm{I}&\mathrm{N}\
\hline
\mathrm{V}&\mathrm{I}&\mathrm{E}&\mathrm{R}

\end{array}$

[sterile pumice]

galois

[stiff estuary]

$\forall\mathrm{E,I,N,V,R} \in X \land 0 \leq X \leq 9$

[sterile pumice]

galois

[stiff estuary]

||821||

I only got half way through the problem then I used a computer to solve it

but I want to know if there is a better way with algebra and modular arithmetic

[torn escarp]

just naively writing it out in modular arithmetic is gross because of carries

[stiff estuary]

I got $1236 \leq \mathrm{VIER} \leq 9840$

[sterile pumice]

galois

[stiff estuary]

yes I started writing all the set notation

[torn escarp]

is there any extra information about the digits

[stiff estuary]

it was a huge mess

[torn escarp]

like each digit only appears once or in descending order or whatever else

[sage fern]

i don't think this is number theory really

i mean there's a little bit but it seems much more like casework and involving upper bounds and things

[stiff estuary]

yes two variables can'tbe the same number

[torn escarp]

why didn't you say that?

[stiff estuary]

sorry

[torn escarp]

is there more you're leaving out

[stiff estuary]

no thats all

[sage fern]

how can it be 9840, that's way too high, ein is a 3 digit number

[stiff estuary]

oh wait

[sage fern]

eh, it's pretty standard for these sorts of questions

[stiff estuary]

I did work out another number

[leaden swan]

It's definitely less than 4k

[stiff estuary]

987x4

[torn escarp]

sure, I'm just giving him a hard time for asking the question and also using a gross amount of set theory notation

[stiff estuary]

I am learning

if there is a better way teach me

[torn escarp]

use english words

[stiff estuary]

ok

will do

[torn escarp]

"the letters are distinct digits of a base 10 number"

something like that

[sage fern]

iiii don't think 987 works? lemme doublecheck

[stiff estuary]

ok

that is the upper bound

[sage fern]

oh, that

i thought you meant you found another solution lol

[stiff estuary]

1236 3940

it must be 4|x

[sage fern]

it's just going to be casework

[stiff estuary]

there is exactly one solution I posted it already in spoiler tag

I have already checked with a computer

but are there are easy tricks that make this simple?

or is it just a lot of crazy set theory

[sage fern]

it's not set theory or modular arithmetic mainly

it's just going to be casework

i think

and one-time tricks

like, v is restricted to between 0 and 3 inclusive

[stiff estuary]

yes

[sage fern]

r is 2, 4, 6, 8, 0

[stiff estuary]

actually

no 0 for v

no leading zero

[sage fern]

you didn't specify that >.>

[stiff estuary]

you never have leading zeros in math

[sage fern]

shhhh

[stiff estuary]

unless there is a decimal

[sage fern]

but anyway e is then restricted based on r

[stiff estuary]

R is even

did you get that?

[sage fern]

yes i said

r is 2, 4, 6, 8, 0

[stiff estuary]

ok

[sage fern]

the e i swapping is the strongest condition i think

[stiff estuary]

yes it totally solved it when I put that in the computer

but how to write that as congruence I don't know

I got lots of intervals

[sage fern]

it's not going to be a congruence imo

it's just going to be casework

i don't think there'll be a clean way to solve this

[stiff estuary]

I got all the intervals easy

[sage fern]

hnngh

[stiff estuary]

but then finding the intersections of all those intervals was crazy big work

[sage fern]

there's just going to be one-time fiddly tricks

this is #competition-math

[stiff estuary]

ok

[sage fern]

it's meant to be long and annoying

[stiff estuary]

I didn't know that there were no tricks

[sage fern]

there are tricks

[stiff estuary]

I just assumed congruences

[sage fern]

there will be shortcuts that reduce the work down to something manageable

[stiff estuary]

something with inequalities using algebra?

[sage fern]

inequalities, eh, only to frame it to begin with

to set initial restrictions

i don't see the other ones

[stiff estuary]

but the e to i thing

[sage fern]

algebra, yes

yeah

[stiff estuary]

if you mod 100 - mod 10 you get the middle digit every time

so what about that?

[sage fern]

uhhhh

you tell me

i don't know wtf to do with that

this isn't really modular arithmetic, for the last time

[stiff estuary]

you can decompose decimal numbers into digits

[sage fern]

krumpf

[stiff estuary]

pretty sure this is number theory

[sage fern]

i think i'm actually going to go sleep now instead

this is just going to be really drawn-out

[stiff estuary]

ok thanks anyway

[sage fern]

nvm found it

https://www.math.uni-bielefeld.de/~sillke/PUZZLES/ALPHAMETIC/ein+ein+ein+ein=vier

gn

[stiff estuary]

wow!

there is it is mod 100 mod 10

ty

[torn escarp]

not a fan, first step is be lucky and pick two digits mod the right thing then the second step is make a huge table

[stiff estuary]

after I got the upper and lower bound and figured out the 4|VIER i HAD 670+ in the set

I didn't even look at them just the order of the set

so then I figured E can't be 0,1,2

then I was at like 450 ish

deleted answers without all unique digits

it was a process

got down to {821,820} then I put another condition on it got back 821

so not once did I manually check it

[sacred junco]

Hint on proving that for every integer n, $3 \nmid (n^2 + 1)$?

[sterile pumice]

LINEAR_ALGEBRA_GUY

[torn escarp]

look at n^2+1 mod 3

[sacred junco]

Yes I tried that, so then n^2 + 1 = 3x + 1, or n^2 + 1 = 3x + 2. But then n^2 = 3x, which does divide if n is 0...

[torn escarp]

part of the point of modular arithmetic notation is so that you don't have to write all that out, you just focus on remainders

just look at n=0,1,2 for each case

[sacred junco]

You say I don't have to write it all out, but if I do write it out then I see that for n = 0 it fails

[torn escarp]

0^2+1 = 1, 1^2+1=2, 2^2+1= 2 none are 0 mod 3, that's all you have to do

you're mistaken, you didn't add 1

[sacred junco]

If n^2 + 1 has a remainder mod 3, then that means we can write it in one of two forms

i) n^2 + 1 = 3x + 1, since the remainder of it can be 1 or
ii) n^2 + 1 = 3x + 2, since the remainder of it can also be 2

So I did add 1?

[torn escarp]

$0^2+1 \equiv 1 \mod 3$ always has remainder 1

[sterile pumice]

Merosity

[sacred junco]

Why can't I write it in that form?

n^2 + 1 is always some integer

So if n^2 + 1 has a remainder of 1, when divided by 3, I should be able to write n^2 + 1 as 3x + 1, for some integer x

[torn escarp]

sure

[sacred junco]

Okay, so n^2 + 1 = 3x + 1..... Then if we subtract 1, we get n^2 = 3x.

[torn escarp]

yep

[sacred junco]

Right so, it does divide for n = 0...

[fervent crest]

You're trying to show 3 doesn't divide n^2+1 my dude

[sacred junco]

[fervent crest]

not 3 doesn't divide n^2

[sacred junco]

So then what is n^2 = 3x?

[fervent crest]

It's just an equation that doesn't have anything to do with what you're trying to prove

[sacred junco]

oh

🥴

[fervent crest]

The statement you wrote there is what you are trying to prove

So you can't just assume that when you are trying to prove this statement

[sacred junco]

So how can I prove it?

[torn escarp]

I pretty much lay it out for you here already

[sacred junco]

\begin{align}
(0)^2 + 1 \equiv 1 &\pmod{3} \
(1)^2 + 1 \equiv 2 &\pmod{3} \
(2)^2 + 1 \equiv 2 &\pmod{3}?
\end{align}

[sterile pumice]

LINEAR_ALGEBRA_GUY

[torn escarp]

yeah

none of those are 0, so you're done

[sacred junco]

Oh alright

Thanks

[torn escarp]

you're welcome 👍

[sleek cove]

thanks

[torn escarp]

@fervent crest is welcome

[fervent crest]

👀

[sleek cove]

nice

[hazy quest]

I have a question, I'm not sure if putting it out here is the right place

I have n digits, each can be between 0...9 inclusive

I am creating a number with these digits. (number can start with 0)

Only constraint is that no 2 consecutive digits can be alike

This would make 10 * 9 * 10 * 9...

possibilities

I'm not sure how to express this in terms of n

[leaden swan]

If n is even,(90)^(n/2)

If n is odd (90)^(n-1)/2 10

[hazy quest]

is there a way to merge those two?

[leaden swan]

$90^{\floor{\frac{n}{2}}}10^{n%2}$

[sterile pumice]

MoonBears-D-

[hazy quest]

ahh, this is cool

I like the mod part

slick

[fair dagger]

Is it really 10×9×10×9…

[hazy quest]

I think so

we can put 10 different digits in the first place

then we can only put 9 in the second bc one is occupied

[fair dagger]

Then 9 for the third one?

[hazy quest]

why?

you may be right

[fair dagger]

Like can't be the same with the second one

[hazy quest]

yes, my thinking was faulty

I was arguing that we can arrange for the third to be some step before or after the second and since the second covers 9 it can cover 10

but that doesn't work

[leaden swan]

Is it just 10*9*9*9*9...

[fair dagger]

I think so

[hazy quest]

10 * 9 * 9 * 10?

[fair dagger]

Fourth also depends on the third

[hazy quest]

yeah

true

good talk, thank you

[fair dagger]

[storm sinew]

https://cdn.discordapp.com/attachments/359052604149465088/794296022016720896/80e40ebe2f5473a80050e87d1b57a070.png does anybody have an efficient method for solving this problem? (without playing with numbers and guessing my way to the answer?) :)

[lusty hornet]

Use AGM @storm sinew

[sacred junco]

Is this a typo?

Show that the set $S=\left{t \in \mathbf{Z}: t^{2} \equiv 4(\bmod 5)\right}$ contains infinitely many elements.

[sterile pumice]

LINEAR_ALGEBRA_GUY

[sacred junco]

\begin{aligned}
&\text { Let } t=5 k+2, \text { where } k \in \mathbf{Z} . \text { Then } t^{2}-4=(5 k+2)^{2}-4=25 k^{2}+20 k+4-4=5\left(5 k^{2}+4 k\right)\
&\text { since } 5 k^{2}+4 k \text { is an integer, } 4 \mid\left(t^{2}-4\right) \text { and so } t^{2} \equiv 4(\bmod 5) \text { . }
\end{aligned}

[sterile pumice]

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

[sacred junco]

Why do they conclude that 4 | (t^2 - 4)?

[lusty hornet]

I think that's a typo, it must be 5| (t^2 - 4)

[sacred junco]

I think so too but I am not completely sure

[lusty hornet]

because this clearly is not divisible by 4, 5k^2 + 4k = 4(k^2) +4k +k^2, so (t^2 - 4) not divisible by 4 every time

it is only divisible by 4 if k is an even number

[storm sinew]

@lusty hornet i already tried that but i couldnt solve it. Could you show me how you'd do it?

[lusty hornet]

that is a useless method which I gave before , sorry. I didn't read it clearly

[lusty hornet]

@storm sinew there is a Brahmagupta Fibonacci identity which gives you all solutions of $a^2 + b^2 = c^2 + d^2$

To work it out , you can do like this, take : $x = p+ iq$ and $y= r+is$, you may know that $|x \bar y| = |x||\bar y| = |xy|$ So, upon solving $|x \bar y| =|xy|$ you would get $\newline$
$(p r + q s)^2 + (q r - p s)^2 = (p r - q s)^2 + (p s + q r)^2$ . So, all the solutions will be of the form: $\newline$
$(a,b,c,d) = (pr+qs, qr−ps, pr−qs, ps+qr)$

[sterile pumice]

Kanishk

Kanishk

[storm sinew]

oh wow, ill check that out. thanks!

[wise oyster]

So, if just seen a proof for this that I understand, where e(a,p) denotes the highest power of p that divides n!.

However

I cannot for the life of me understand how it leads us to this corollary

any help, whether intuitive or just a proof would help me out here

i feel like im missing something super obvious but i cant figure it out

[torn escarp]

I think it might be clear if you give that function a name, $s_p(n)$=sum of digits of n when written in base p

[sterile pumice]

Merosity

[torn escarp]

then write out what e(binomial(n,k), p) is

then you can start to reason through what happens to the sum of digits when adding and carrying

also I'd probably write it more symmetrically

$\binom{a+b}{a} = \binom{a+b}{b} = \frac{(a+b)!}{a!b!}$

[sterile pumice]

Merosity

[torn escarp]

that way you can think of adding just plain a+b

[wise oyster]

why thing is im not sure how to figure out e for binom(n,k) in the first place

[torn escarp]

oh, binomial is just a product of 3 factorials

[wise oyster]

dont know why i wrote why

yeah

[torn escarp]

and the e function (the p-adic valuation lol) is additive

[wise oyster]

im having trouble reasoning on whther or not that means i can just multiply out the e function for the other ones

oh true id add

ahh

ill give this a shot later

[torn escarp]

ok good luck

[wise oyster]

oh yeah just realised you must be really familiar with this stuff due to p adics no?

[torn escarp]

the main thing to think about is what I mentioned here, how the sum of digits changes when you carry, probably just write something out and think about it

[torn escarp]

yeah, very lol

[wise oyster]

yeah ill work through a few examples

[torn escarp]

personally I prefer to write legendre's formula as $v_p(n!) = \frac{n-s_p(n)}{p-1}$

[wise oyster]

didnt notice when doing this it was related to p adics

[sterile pumice]

Merosity

[torn escarp]

and the completely additive property (it's basically a logarithm base p, blind to other powers) $$v_p(xy) = v_p(x)+v_p(y)$$

[sterile pumice]

Merosity

[wise oyster]

aight thanks ill give this a look

[torn escarp]

same v_p(x) = e(x,p) function so nothing new here just change of notation

[wise oyster]

i think my main issue is being a little too unfamiliar with expressing numbers in other bases

like i get it but i dont work with it enough to get quick intuitions

[torn escarp]

yeah, in particular you can think of getting the digits by repeatedly looking at the number mod p and subtracting off that remainder and dividing by p

dunno if that's really that helpful to say, you probably already know that

[wise oyster]

hm actually hadnt thought of it

[torn escarp]

like say you want 12 in base 2, well first you know it ends in two 0s

[wise oyster]

but that makes sense yeah

[torn escarp]

just like base 10 the number of 0s is the number of times 10 goes into it

then you think, what's 3 in base 2?

[wise oyster]

i mean for binary i tend not to have problems from having worked with it a lot

[torn escarp]

so in all 12 is 1100 in base 2

yeah true, personally I am most comfortable with base 2, 3, 5

[wise oyster]

in binary it's a little easier cause you can think of just activating or deactivating powers

instead of having coefficients

[torn escarp]

you could think of base 3 that way if you use a different set of coefficients

you could use 1, 3^n and -3^n lol

[wise oyster]

that's fair

[torn escarp]

maybe fair, but kind of silly hah

doing that means you need to change your rules for arithmetic, like what is carrying now?

[wise oyster]

my problem with thinking about bases is we talk about other bases but still write with base 10 numbers so it's a little confusing

[torn escarp]

yeah I know what you mean

I got too used to it though that I say confusing things about base notation without realizing it lol

[wise oyster]

just realised that what you said about taking a number mod p, subtracting the remainder and dividing is what's being used in the proof of the earlier result anyways lol

im an idiot

[torn escarp]

haha

[wise oyster]

yessss

i figured it out

[torn escarp]

awesome

[wise oyster]

thanks a bunch

you really helped me out

[torn escarp]

yeah you're welcome

now you're basically ready to compute the radius of convergence of the p-adic exponential series 😎

[wise oyster]

noice

i mean this is part of an elementary number theory course so i dont think they get to p adics

MIT opencourseware is a godsend

[torn escarp]

haha yeah probably not

[wise oyster]

is there a particular piece of notation used to denote the number of carries you get when adding a and b in base p

i like to have concise notation in my notebook and if i can avoid inventing it, the better

[torn escarp]

none that i'm aware of, the only time I ever think about the number of times I carry is when proving that problem lol

[wise oyster]

haha nice

[torn escarp]

I think that I said something slightly wrong earlier about your notation

$v_p(n!) = e(n,p)$

[sterile pumice]

Merosity

[torn escarp]

your e function only is talking about the number of prime powers in the factorial

the p-adic valuation can have any rational number in it

I think that was probably part of the confusion about how to get the binomial out of it earlier now that I realize that

[wise oyster]

yeah i changed notation anyways

it's aight

adopted the v notation

though i still use e

[torn escarp]

yeah it's easier, cause it's just log rules

might as well also mention, but probably not useful to you

$|x|_p = p^{-v_p(x)}$ this is the p-adic absolute value

[sterile pumice]

Merosity

[torn escarp]

and $x \equiv y \mod p^n \implies |x-y|_p \le p^{-n}$

[sterile pumice]

Merosity

[torn escarp]

I guess to really make use of that you have to know the ultrametric inequality at a minimum but I think maybe that's already too much so I'll stop haha

[wise oyster]

i need to redigest this for the 3rd time

right okay yes

so $|54|_3 = \frac{1}{3}$ for example?

[sterile pumice]

Little Narwhal

[wise oyster]

wait no

$\frac{1}{27}$

[sterile pumice]

Little Narwhal

[torn escarp]

yup

[wise oyster]

forgot to actually exponentiate the p

[torn escarp]

hah

[wise oyster]

also is that an iff or just an implication

the second statement

wait done answeer that

lemme find a counterexample

[torn escarp]

good question 😛 yeah, there is a common use case when it's <=

[wise oyster]

$|x-y|_p \leq p^{-n} \implies v_p(x-y) \geq n$. So there is a power of p $e \geq n$ such that $p^e|x-y \implies x \equiv y \mod p^e \implies x \equiv y \mod p^n$

is this correct?

[sterile pumice]

Little Narwhal

[torn escarp]

almost, the last => is not right

[wise oyster]

why not?

if $p^e|x-y$ then $p^n|x-y$ since $e \geq n$

[sterile pumice]

Little Narwhal

[torn escarp]

oh nevermind that's fine sorry haha

[wise oyster]

aight cool

[torn escarp]

although this is true it doesn't quite tell you when it's invalid

there is a restriction on n that has to pop out

[wise oyster]

hmm

[torn escarp]

I guess as a hint, remember x,y are rational numbers

[wise oyster]

rationals or integers?

i didnt know you could use mod notation for rationals

[torn escarp]

you can't haha

not if the denominator has a power of p in it at least

[wise oyster]

oh okay yeah i was trying to figure that out in this context

[torn escarp]

$|x|_p$ is perfectly fine with say, $|1/p|_p = p$

[sterile pumice]

Merosity

[torn escarp]

so it breaks when $n \le 0$, otherwise it's fine

[sterile pumice]

Merosity

[wise oyster]

right

is that the only restriction on n though?

[torn escarp]

yeah that's it

one of the reasons p-adics are useful is it lets you divide by p, which you can't really do mod p^n

[wise oyster]

ah okay

yeah i had seen that but i thought there was more

[torn escarp]

and so that's basically what's going on there, we're moving up from being in these rings to a field

[wise oyster]

oof i havent really done any ring and field theory

i just know what they are

[torn escarp]

ah, well mod p is a field when p is prime

mod p^n is never a field for n>1 since it has 0 divisors

[wise oyster]

so what you say makes sense at least

[torn escarp]

in other words, things that multiply to make 0 that aren't themselves 0

namely, p*p=0 mod p^2

[wise oyster]

right

[torn escarp]

it's kind of an irritating thing to have to worry about division by p, but when you work with p-adics you still have the modular arithmetic stuff and you can always 'round down' to the number in mod p^m in the end

I guess I should say, every time you're using p-adics you pretty much are using base p, since that's naturally how you think of digits mod p^n anyways

[wise oyster]

yeah

from what we discussed earlier

[torn escarp]

I could show you some simple problems maybe to play with if you want, trying to think of stuff that doesn't require too much work but show some tricks

[wise oyster]

that would be awesome yeah

sorry for the late reply i was writing the proof in my notebook

[torn escarp]

I guess it's worth mentioning we also have that infinite sums work here too, so long as they get larger and larger powers of p in them

[wise oyster]

wdym

[torn escarp]

$|p^n|p = p^{-n}$ so as n gets larger, $$\lim{n \to \infty} p^n = 0$$

[sterile pumice]

Merosity

[wise oyster]

oh yeah

[torn escarp]

you can think of this as being, p^n is 0 mod p^k if you make n large enough

another thing to mention

[wise oyster]

fair yeah

[torn escarp]

in $|x-y|_p=p^{-n}$ that n is the number of digits they have in common when written in base p

[sterile pumice]

Merosity

[wise oyster]

right cause then those become 0 in the subtraction

substraction*

wait actually im missing the point i think

[torn escarp]

so ok here's a problem for you, for an odd number x, look at 3x+1. How are the digits of x in base 2 related to the number of times you can divide 3x+1 by 2?

[wise oyster]

lemme pull out some paper

well what's for sure is 3x+1 is at least divisible once by 2

[torn escarp]

yup

[wise oyster]

and x being odd guarantees that the first digit in base 2 is one

so i imagine that generalises lemme see

all 3x+1 does is offset the base 2 representation of x twice to the left

[torn escarp]

I guess to be particular, let's say you divide by 2 exactly n times, how do the digits of x look like in base 2 specifically?

[wise oyster]

oh wait i messed up

okay okay im getting somehwere

wait i just found something only to realise that wasnt at all what you were asking anymore haha

[torn escarp]

oh what is it

I just tried to make it more precise, not different haha

if you answered the original thing to some extent that's probably a good step

[wise oyster]

that $S_2(3x+1) = 2S_2(x) - 1$ but that doesnt have anything to do with the original thing anymore XD

[sterile pumice]

Little Narwhal

[torn escarp]

ah yeah haha

the sum of digits is not quite what we want

[wise oyster]

yeah idk what i was thinking i went off ona random tangent

now im having trouble recalibrating my brain

[torn escarp]

|x-y|_p or v_p(x-y) is more what we need to look at to see if something has digits in common with something else

[wise oyster]

oh

no im in a full brain fart moment i need to trigger a reset haha

[torn escarp]

I guess maybe I should give a bit more help I think I might have dropped you in the deep end of the pool and let you drown a bit

but that's good for you 😛

[wise oyster]

im having so much trouble concentrating idk why

[torn escarp]

I guess two important things to notice:

$|3x+1|_2=2^{-n}$ means 2 divides 3x+1 exactly n times

[sterile pumice]

Merosity

[wise oyster]

and that n is the number of 0s at the end of the binary representation of 3x + 1 right?

[torn escarp]

$|x-a|_2=2^{-m}$ means x and a have exactly m digits in common from right to left

[sterile pumice]

Merosity

[torn escarp]

yeah exactly

number of 0s on the right is the number of times it's divisible by p in base p

[wise oyster]

4x +1 -x = 3x + 1 so that means that 4x + 1 and x must have n digits in common from right to left

is that gonna help?

[torn escarp]

for my solution in mind, nope haha

basically I'm thinking about both of these absolute values I've written above

and now thinking, how do I determine the digits of a?

that will basically answer our question of how m (how the digits of x look) and n (the number of times 3x+1 is divisible by 2) relate

[wise oyster]

okay

the number of pairs of digits in x is the same as the number of times 3x + 1 is divisible by 2, minus 1?

or am i completely off

cause here's my reasoning

wait nvm i messed up

thought there was smth weird

[torn escarp]

cool, I was making tea

I don't want to let it drag on too much longer cause I think I haven't really shown you enough examples of how it works to really expect you to solve it I think

[wise oyster]

i dont like brain farts like this

[torn escarp]

besides it's tricky haha

[wise oyster]

especially with a binary question, got a question on binary in an entrance exam and got a brain fart and figured it out right after the exam

was so pissed at myself

[torn escarp]

I wanted to let you struggle a bit so you get an idea of what things are

ah that sucks haha

so here's what we have $|3x+1|_2=2^{-n}$ so first thing we can do is factor out the 3

[sterile pumice]

Merosity

[torn escarp]

$|3x+1|_2 = |3|_2 |x+\tfrac{1}{3}|_2$

[sterile pumice]

Merosity

[wise oyster]

lemme just convince myself that that's legal

yeah okay

[torn escarp]

since $|3|_2=1$ we're already closer to $|x-a|_2$ like we want to relate it to

[sterile pumice]

Merosity

[torn escarp]

$|3x+1|_2 = |x- \tfrac{-1}{3}|_2$

[sterile pumice]

Merosity

[torn escarp]

ok the problem is, how do we determine the base 2 expansion of -1/3?

it's not even an integer

seems wrong

[wise oyster]

infinite expansion or smth right

[torn escarp]

yeah, well mod 2, 4, 8, etc we have -1/3 is perfectly well defined

so we can pull out the digits that way looking each time

[wise oyster]

so we take an infinite series

yeah that makes sense

[torn escarp]

yeah, but we can do better

$\frac{-1}{3} = \frac{1}{1-4} = 1+4+4^2+4^4+\cdots = ...010101$

[sterile pumice]

Merosity

[wise oyster]

ah yeah

[torn escarp]

so the number of times you divide 3x+1 by 2 is exactly how much the digits of x look like ...01010101

[wise oyster]

ahhh

[torn escarp]

the first digit it misses by is where you divide

[wise oyster]

so for x = 110010101 3x + 1 is divisible 5 times?

6 times sorry

[torn escarp]

6 times

yeah good

so technically we didn't probably need to use all this stuff but it was kind of convenient

but we sort of reasoned about an entire bunch of mod 2^n things simultaneously which was nice

[wise oyster]

wait so why was x being odd important here

ah cause if x is even then 3x + 1 is never divisible by 2 anyways im stupid

i even said it earlier lol

[torn escarp]

haha

nice

[wise oyster]

so say we considered 8x + 1 instead

then when we decompose

[torn escarp]

sure, we could consider any other similar type of problem

[wise oyster]

we'd have an issue with |8| right

since that becomes 1/8

[torn escarp]

I just made this cause it was like, related to the collatz conjecture I guess

and it was simple enough to not need the strong triangle inequality

[wise oyster]

ah

[torn escarp]

yeah

in fact maybe now is a good time to show it

$|x+y|_p \le \max(|x|_p,|y|_p)$

[sterile pumice]

Merosity

[torn escarp]

but even better, when $|x|_p \ne |y|_p$ then $|x+y|_p = \max(|x|_p,|y|_p)$

[sterile pumice]

Merosity

[torn escarp]

so like in general all integers satisfy $|x|_p \le 1$ and so if we look at any integer x, $|8x+1|_2 = 1$

[sterile pumice]

Merosity

[wise oyster]

im trying to convince myself of the max thing

[torn escarp]

yeah there are two max things to prove here, that it really does satisfy the first version and the second is when they're nonequal it becomes equality

to convince yourself, think about two numbers written in base p

[wise oyster]

wait i see why

[torn escarp]

and what happens when you add them

[wise oyster]

you can see from a decomp i think

like $|x+y|_p = |x|_p|1+\frac{y}{x}|_p = |y|_p|1+\frac{x}{y}|_p$ and those fractions are gonna impact the modulus depending on the distance between x and y mod powers of p

[sterile pumice]

Little Narwhal

[torn escarp]

yeah, maybe write $x=p^a s$ and $y=p^bt$

[sterile pumice]

Merosity

[torn escarp]

with $|s|_p=|t|_p=1$

[sterile pumice]

Merosity

[wise oyster]

hmm yeah

and if $|x|_p = |y|_p$ then $a=b$ so the fractions become $\frac{s}{t}$ and $\frac{t}{s}$

[sterile pumice]

Little Narwhal

[torn escarp]

yeah, I'm thinking more like, |x|=|y| means a=b so you have

$p^{-a}|s-t|_p$ and so now either they share no digits in common and $|s-t|_p=1$ or they do and $|s-t|_p<1$

[sterile pumice]

Merosity

[wise oyster]

wait why s-t shouldnt it be s+t

[torn escarp]

oh whoops, doesn't matter really

[wise oyster]

fair

just rename variables

[torn escarp]

I guess maybe we should show other things like multiplication |xy|=|x||y| but we've assumed that

[wise oyster]

i mean i see why that's true

[torn escarp]

like in our case |-t|=|-1||t| is probably good to see

[wise oyster]

yeah

[torn escarp]

$$t=\sum_{n=0}^\infty a_np^n$$

[sterile pumice]

Merosity

[torn escarp]

$$-1 = \frac{p-1}{1-p} = \sum_{n=0}^\infty (p-1)p^n$$

[sterile pumice]

Merosity

[torn escarp]

so here's the digit expansion of -1, just p-1 repeating

[wise oyster]

huh interesting way to write -1

[torn escarp]

now we're not gonna multiply them, but we could

we can directly think about what we need to add to t to make -1

then add 1 to that to get 0

$$f(t) = \sum_{n=0}^\infty (p-1-a_n)p^n$$

[sterile pumice]

Merosity

[torn escarp]

see how p-1 is the largest digit in base p

this means p-1-a_n is also another digit and so this is its digit expansion

and satisfies f(t)+t = -1

[wise oyster]

yeah

[torn escarp]

so if we want -t we just look at

-t = 1+f(t)

[wise oyster]

right

[torn escarp]

and then check that |t|=|1+f(t)|

[wise oyster]

and we saw that from the fact that it's equivalent to similar digits

[torn escarp]

yeah pretty much

like if it has all 0s there then it becomes p-1

but when you add 1 it's like

let's look at an example in base 10

32000 would become 67999

and adding 1 to this gets you 68000

well whoopse not quite

it becomes ...999967999

I just disregarded the 9s to the left as irrelevant

[wise oyster]

right yeah i was a little confused

[torn escarp]

adding 1 to that gets you ...999968000

the point is the number of 0s on the right is identical

[wise oyster]

yeah

[torn escarp]

the negative sign is kind of superfluous in this notation

[wise oyster]

i guess there's still one result we've been using a lot that im not too confident on, and that's that the number of digits which are the same from right to left of a and b is the same as $v_p(a-b)$

[sterile pumice]

Little Narwhal

[wise oyster]

wait nvm

i see it

[torn escarp]

yeah lots of stuff going on haha

[wise oyster]

we discussed this before haha

right okay so that max result makes sense now

[torn escarp]

yeah, and do you see why it's equal to the max when they're not equal?

[wise oyster]

yes

because that's when s and t share digits

[torn escarp]

or don't you mean?

[wise oyster]

yeah mb

[torn escarp]

yeah in p-adics things are a bit nicer cause carrying happens to the left

in the reals you're like fighting carrying to the left with getting smaller to the right

but in the p-adics everything just goes to the left haha

[wise oyster]

not sure what you mean

[torn escarp]

like when you add fractions, 0.1+0.9 = 1.0

small numbers can end up giving you digits to the left

in the 10-adics however if you add 1+9=10 you will only get smaller or the same size

[wise oyster]

oh okay yes

[torn escarp]

if carrying happened to the right we'd be in the same kind of situation

like for example, for a series to converge in the p-adics $\sum_{n=0}^\infty a_n$ all you need is for $\lim_{n \to \infty} a_n=0$

[sterile pumice]

Merosity

[wise oyster]

im having a bit of trouble understanding what the a_n is here

[torn escarp]

so all the annoying limit tests etc of real analysis/calculus aren't around

[wise oyster]

the p adic modulus of a number?

[torn escarp]

oh I thought you took calculus 2 or something maybe I'm over assuming

a_n are terms of an infinite sequence

[wise oyster]

yeah no iget that

but like

[torn escarp]

like 1, 1, 2, 6, ...

[wise oyster]

what do you mean by a_n "in the p adics"

[torn escarp]

$$x=\sum_{n=0}^\infty n!$$ is a well defined p-adic number

[sterile pumice]

Merosity

[torn escarp]

I guess I have to back track a bit I forget what we covered exactly

[wise oyster]

right so you mean $\lim_{n\to\infty}|a_n|_p$

[sterile pumice]

Little Narwhal

[wise oyster]

not the limit on a itself

[torn escarp]

well the definition of a limit is the same as in real analysis just with the absolute value changed out

[wise oyster]

ohhh

so it's a limit in the p adic numbers

right okay that's gonna be a little hard to reconcile with

[torn escarp]

here we say $\lim_{n \to \infty} a_n = a$ if for all $\epsilon>0$ we have an N such that $n>N$ implies $ |a_n-a|_p <\epsilon$

[sterile pumice]

Merosity

[torn escarp]

epsilon is real

[wise oyster]

woo epsilon delta

[torn escarp]

haha

[wise oyster]

cant wait to be doing those next year

and die

[torn escarp]

yeah haha

I didn't much care for analysis when I originally took it

but I grew to like it eventually lol

[wise oyster]

i keep pushing it back

but i know itll eventually come

[torn escarp]

yeah takes time to really think about and internalize the definitions and feel like they're natural

[wise oyster]

im gonna head off now it's getting late

but thanks for this it was very interesting though i had a lot of brain farts

[torn escarp]

yeah take it easy, haha it was fun

later

[grave carbon]

I was wondering if someone could help me on how to prove this. I’m not really sure how I would begin.

[leaden swan]

Do you understand the usual base 3 representation?

$\sum_{i=0}^{n}c_i 3^i$ where each coefficient is 0,1 or 2

[sterile pumice]

MoonBears-D-

[leaden swan]

Every positive integer can be written in this form in a unique manner

Now, replace wherever 2 occurs with (3-1) (i.e, 2*3^i becomes 3^(i+1)-3^i)

@grave carbon

This shows every non zero integer has a representation of that form(For negative integer a,just find the the representation for -a and multiply that with -1)

You have to show that's unique

[grave carbon]

Thank you, I’ll work with this @leaden swan

[wise oyster]

similarly to what merosity and i were discussing yesterday, consider looking at n mod 3^j

[sacred junco]

I need help with this: Disprove the statement: There exist two distinct primes p and q such that the six integers pq +- 2, pq +- 4, and pq +- 6 are all primes.

Obviously p, q need to be odd for it to be even remotely possible

But the product of two odds + an even = odd, so that doesn't get me anywhere.

[wise oyster]

you also cant have p or q be 3

[sacred junco]

Why?

[wise oyster]

because then pq +- 6 mod 3 is 0

so it isnt prime

[sacred junco]

Oh right

[wise oyster]

i cant figure out more right now im thinking

[sage fern]

probably just pigeonhole it somehow, wrt. 3 or 5

actually yeah just 3 works

[sacred junco]

What are you talking about?

[sage fern]

pq = r

one of: r = 3s; r = 3s + 1; r = 3s + 2 must be true

[wise oyster]

ahhh

[sacred junco]

Why 3?

[wise oyster]

for any of those cases one of the others is congruent to 0 mod 3

[sage fern]

but that's equivalent to the cases given mod 3

[sacred junco]

Why not 2?

[sage fern]

well the difference is 2

so they could all be odd

it doesn't work

[wise oyster]

in fact they have to all be odd

[sacred junco]

I don't understand that reason 😦

[wise oyster]

thanks @sage fern i was going of on a wild goose chase

@sacred junco since they all differ from pq by some multiple of 2 they are all congruent to pq mod 2

so you cant reason any differently between them

meanwhile pq +- 2 = pq + 2 mod 3, pq +- 4 = pq + 1 mod 3 and pq +- 6 = pq mod 3

[sacred junco]

Ohhh

[sacred junco]

That makes sense I guess

[wise oyster]

so for the three scenarios of pq where either pq = 0 mod 3, pq = 1 mod 3 or pq = 2 mod 3, one of pq +- 2, pq +-4 and pq +- 6 = 0 mod 3

[sacred junco]

But how did you know to use 3?

[sage fern]

5 would probably also work

7 probs wouldn't, there's not enough numbers

[wise oyster]

any number smaller than 6 that is coprime with 2 4 and 6 would work i believe

so just 3 and 5

[sage fern]

anyway so now there's just the fiddly bit where one of the numbers can be 3 and it dodges the not-prime thing because it having a factor of 3 is fine because it is 3

which is why there's 6 numbers, not 3

[wise oyster]

yeah cause the +- guarantees that two numbers will be congruent to 0 mod 3

[sacred junco]

[sage fern]

you've got it covered, right?

[sacred junco]

What do you mean by dodges?

[sage fern]

ok so we're showing it's not prime by pinning it down to reveal that one of them has to have a factor of 3

but if that one is in fact 3 it could still work, because 3 | 3 but 3 is still prime, obviously

but if there's one there's another, so it's all fine

[sacred junco]

Alright

[wise oyster]

aight i just need a confirmation on a fact that I believe Ive proved but Im never confident so I just want to make sure that this fact is actually true? Would someone be willing to confirm that $\binom{p^i-1}{k}$ is not divisible by $p$ for $0 < k < p^i$ and $p$ prime?

[sterile pumice]

Little Narwhal

[wise oyster]

and i > 0

i dont need a proof because i believe i have one, just want to make sure the statement is true

which granted i should be convinced of by my proof but just in case

[sage fern]

p = 2, i = 3, k = 1; 7C1 = 5040, 2 | 5040

[wise oyster]

7C1 is not 5040?

[sage fern]

it isn't?

[wise oyster]

nC1 = n

[sage fern]

oh argh

what am i even doing

[wise oyster]

lol thanks though

i actually already have confirmation that (2^i - 1)Ck is odd, i was trying to generalize in coming up with my above statement

[sage fern]

can't think of any counterexamples

[wise oyster]

ima look it up actually shouldve probably done that first

[wise oyster]

cant find any mentions of it

(though i did get distracted)

[abstract flax]

@wise oyster Care to share your proof, then we can check it at least?

[wise oyster]

Yes lemme just finish my lunch

[abstract flax]

Cool, I think it might be true

It's definitely true

[wise oyster]

right so

thanks for the confirmation

here's the proof

it's based on a statement merosity helped me prove yesterday, which states that the highest power of p with p prime to divide $\binom{n}{k}$ is equal to the number of carries you get when adding k and n-k in base p

[sterile pumice]

Little Narwhal

[wise oyster]

in the case n = p^i - 1, note that the base p representation of n is (p-1)(p-1)....(p-1) with i digits

when i add k and n-k in base p, i need to get that representation

but note that the last digit cannot have been made from a carry

so the last digits of k and n-k when added do not make a carry

this then implies that the next digit cannot have been made by a carry either and so on

more rigorously youd show this by induction

since there are no carries when adding k and n-k, the biggest power of p to divide $\binom{p^i-1}{k}$ is $p^0$

[sterile pumice]

Little Narwhal

[wise oyster]

so the result follows

[abstract flax]

Interesting. I don't know the carry thing, but I'll look up to find it

[wise oyster]

yeah it's a bit far up

[abstract flax]

Alternatively

[wise oyster]

just scroll a lot

[abstract flax]

There's Lucas's theorem (i just found it, didn't know about it)

[wise oyster]

huh, even more general

[abstract flax]

From this it follows that (m choose n) is divisble by p iff n has a base p digit greater than m's

But since all the digits of p^i-1 are maximal, this cannot be

[wise oyster]

yeah

thaniks for showing me that theorem, are you aware of a proof of it that isnt too complicated?

[abstract flax]

https://en.m.wikipedia.org/wiki/Lucas's_theorem

Look at the ones on Wikipedia

[wise oyster]

yeah just did that

the generating functions one seems approachable

[abstract flax]

Good luck with it then. I want to learn more NT. It's fun lol.

[wise oyster]

yeah ive recently started and it's hella interesting

learning from this : https://ocw.mit.edu/courses/mathematics/18-781-theory-of-numbers-spring-2012/lecture-notes/ and various other online sources when confused or want more info

and of course all you wonderful folks on the server

huh the proof for lucas's theorem is surprisingly simple

[abstract flax]

Thanks, I'll look at that too

[wise oyster]

ugh okay i said lucas's proof was easy at first but that last equality for the generating functions proof took me a while to understand. Not incredibly intuitive I wonder if there's a nicer way to split that last step into smaller steps

[sacred junco]

Problem: Let $a_1, a_2, \dots, a_r$ be odd integers where $a_i > 1$ for $i = 1, 2, \dots, r$. Prove that if $n = a_1 a_2 \cdots a_r + 2$, then $a_i \nmid n$ for each integer $i ~ (1 \le i \le r).$

---

Suppose the contrary, that if $n = a_1 a_2 \cdots a_r + 2$, then $a_i \mid n$ for each integer $i ~ (1 \le i \le r).$

Observe that each $a_i$ is odd, so $\prod_{1 \le i \le r} a_i$ is odd by a previously proven result of the product of odd being being odd.

Without loss of generality, let $a_i = a_1.$ Then since $a_1 \mid n$, let $n = a_1 x$ for some integer $x$. Then $$\prod_{1 \le i \le r} a_i + 2 = n \implies \frac{\prod_{1 \le i \le r} a_i + 2}{a_1} = x.$$ And $x$ is an integer, so the sum $$\prod_{2\le i \le r} a_i + \frac{2}{a_1}$$ is an integer, except it is not since $a_1$ is odd and larger than $1$, so it can't be an integer and thus we have a contradiction. One remark is that we set $a_i = a_1$ to make the proof easier to follow and keep our notation tidy, but we didn't use a fact that is exclusive to $a_1$.

[sterile pumice]

LINEAR_ALGEBRA_GUY

[sacred junco]

Does this proof work?

[abstract flax]

First line is wrong

The contrary would be that there is an integer i for which ai divides n

Not that each ai divides n

[wise oyster]

same misconception as your question from the other day with the negation of a for all statement @sacred junco

[sacred junco]

Yeah

I know

That was an accident

@wise oyster @abstract flax The proof still works though, just have to change for "for each a_i" into "exists an a_i, suppose a_1 is the one that divides n"

Right?

[abstract flax]

The proof is fine, but it would be a lot cleaner if you just used divisibility notation

Do you know a | b as notation for a divides b?

[wise oyster]

yes cause they used it lol

[sacred junco]

Well yes considering I used it

[abstract flax]

Well, do you know the result that if a |b and a|c then a|(b+c)?

[sacred junco]

Yes

[wise oyster]

just use that

[abstract flax]

If ai |n, then ai |(n-a1a2...an) = 2

So ai divides 2, which is a contradiction

[wise oyster]

^^

[sacred junco]

Well first of all a_i | (n - a1a2 * ... * a_n) = 2 doesn't really make sense?

Because a | b tells us that a divides into b, not that it's equal to something?

[abstract flax]

I mean ai divides the expression in the brackets, and that expression equals 2

So ai | (n-a1a2...ar)

But n-a1a2...ar = 2, so ai | 2

[sacred junco]

Right

That's basically my proof just in a bit more detail

[abstract flax]

Well, unnecessarily detail since you aren't using already proven results

And it's not exactly the same

With more details, it would be. Suppose ai divides n. Then n = ai(q) for some q. So 2 = ai(q-a1...a(i-1)a(i+1)...ar) which is impossible.

[torn escarp]

somewhat related, suppose you're wanting to look at the taylor expansion $$\sqrt{1+x} = (1+x)^{1/2} = \sum_{n\ge 0} \binom{1/2}{n} x^n$$ which comes from repeated differentiation, so you naturally have the polynomial $$\binom{m}{n} = \frac{1}{n!} \prod_{k=0}^{n-1}(m-k)$$

[sterile pumice]

Merosity

[torn escarp]

@wise oyster turns out the only primes in the denominator of $\binom{1/2}{n}$ is 2, and this is general, you can show it from the p-adic absolute value

[sterile pumice]

Merosity

[torn escarp]

maybe not the direction you were headed in, since now this is considering rational numbers in the binomial coefficient lol

[wise oyster]

yeah but still an interesting fact

ive rounded off on my notes on binomial coeffs for now though and ill get back to them later, i still havent really gotten to congruences yet (though thankfully im already familiar with them) so i wanna move on lol

ill get back to binomial coeffs when i decide to write down the proof for lucas's theorem

[sacred junco]

Hi

[wise oyster]

👋

[hexed echo]

Problem: Solve the diophantine equation, P(x,y) = y^2-x^3+5x over rationals/Integers.

[lusty hornet]

over rationals or only over integers? @hexed echo

[hexed echo]

Both

[lusty hornet]

I thought of this, y^2 = x^3 - 5x , any integer mod 5 is 0, 1, 2,3,4, the squares of those mod 5 are 0,1,4,4,1 and the cubes of those mod 5 are 0, 1,3,2,4 "respectively" , so LHS= y^2 mod 5 takes values 0,1,4,4,1 while RHS = x^3 + 5x mod5 takes values 0, 1,3,2,4 , now it is clear, that we take only the matching remainders. so the solutions are of the form (x,y) = { ( 5a+1, 5b+1) , ( 5k+2, 5l+4) , ( 5u+3, 5v+4), ( 5t+4, 5q+1) } a,b,k,l,u,v,t,q are integers

so I thought about integers

I don't know if this is really the right way to do it though , tell me if something is wrong

@hexed echo

[hexed echo]

Yeah

[lusty hornet]

we can write a in terms of b as it is just a quadratic like (5a+1) = sqrt ((5b+1)^3 -(5b+1))

and you can do it further

[hexed echo]

It's related to elliptic curves I think

[lusty hornet]

similarly we can write k in terms of l

is this method wrong to do for integers?

I haven't studied elliptic

[hexed echo]

I posted it only because of my curiosity.

[lusty hornet]

I haven't even seriously studied number theory till now , only bits of it from here and there

so what do you think of my method?

[hexed echo]

Are you in University?

[torn escarp]

once you have come up with solutions mod 5, you can use hensel lifting to lift them to higher and higher powers of 5

[hexed echo]

Hmmm

[lusty hornet]

@torn escarp could you tell me if I have the right approach for integer solutions?

[torn escarp]

in theory this gets you all integers and rationals that have no 5 in the denominator

but it also gets you a bunch of extra 5-adic ones as well so

[hexed echo]

It's not like the solution I want

[torn escarp]

it's like saying you can solve it in the reals in a sense

in other words, it's just not really precise enough information without doing some other work too

what work, that I don't know, just keep trying random tricks, maybe there's something you can try in particular

I don't know much about elliptic curves either

[hexed echo]

I want all the SOLUTION s

But rational and integral

[torn escarp]

lol

I was just responding to Kanishk

wolfram alpha says there are 5 integer solutions but I don't know if that list is exhaustive

@hexed echo what have you tried?

[torn escarp]

I typed up a bit of basic 5-adic stuff for the problem earlier and almost forgot, it's probably alien looking so I added a bit of annotation in there. http://mathb.in/48570

[sacred junco]

solve over the integers, n^2-n-11=k^2

n and k are not distinct

[sacred junco]

pls help me

[lusty hornet]

let us simplify it a bit, I will write in(x,y) , ok, \newline $x^2 -x -11 = y^2 \Rightarrow x^2 - x -(11+ y^2) =0 \Rightarrow x =\frac{ 1 \pm \sqrt {45 + 4y^2}}{2}$ now you have to solve $45 + 4y^2 = m^2$ where m is an integer, $4y^2 - m^2 = -45 \Rightarrow 4y^2 \equiv m^2 $(mod 3)

I think you can solve further on your own, using Pell's equation ? @sacred junco

[sterile pumice]

Kanishk

[sacred junco]

thanks a lot

idk if i can solve further but i try

i dont know so good pell’s equation

[lusty hornet]

@sacred junco you can ask again, if you can't

[sacred junco]

i cant........

[wise oyster]

so when looking at the case p = 1 mod 4, it seems the only characteristic of p that makes the argument possible is that p is odd. Yet when p = 3 mod 4 this is also the case. Without considering the part of the proof that shows that p = 3 mod 4 wouldnt work, where does the argument that it works for p = 1 mod 4 breakdown for p = 3 mod 4?

alright nevermind i figured it out

p-1/2 is odd when p = 4k + 3 aight

[sacred junco]

Suppose a and b are fixed integers and let c = ax+by, where x and y are arbitrary integers. Does anyone have any ideas for an algorithm to compute the smallest value of |x| such that |c| < |x| for some y? If it helps anything, a and b can be assumed to be relatively prime, but in the case I want to solve they are on the order of 20 digits. I am currently running what is basically a brute force algorithm, which involves looping over n modding a*n out by b (call that value m) and taking the minimum of m and |m-b|. But this is quite slow and I am not sure it will finish in a reasonable amount of time

[broken igloo]

hmm, there's LLL, probably

no idea though, I'm just putting it as an option while thinking

so you want |ax|<|x| mod b

[sacred junco]

also I might add, it is not necessarily the case that there is a good algorithm, since it's a part of a problem that I mostly made up

[broken igloo]

yeah, so with LLL, you can choose vectors
(b 0)
(a 1)
and you should get
small small
but that's all I got so far

[broken igloo]

oh wait @sacred junco found a heuristic, choose these vectors
(b 0)
(a 1-epsilon)
which means you have a basis vector
(c, (1-epsilon)x)
so, if epsilon is well chosen, you'll expect c and (1-epsilon)x to be about the same in magnitude, so |x|>|c|...

https://en.wikipedia.org/wiki/Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm

[sacred junco]

hmm I don't know anything about LLL and don't understand

[wise oyster]

how do we know that f'(a) has an inverse mod p?

it's the only step of the proof im unclear on

nvm i just figured it out

it's always like this haha

[wise oyster]

aight another question that i hope ill figure out on my own before you answer

This is for a proof that there are primitive roots mod m iff m = 1,2,4, p^e, 2p^e

I dont get how g being odd implies that it is a primitive root mod 2p^e

i imagine there's a way to combine g^(phi(p^e)) = 1 mod 2 and g^(phi(p^e)) = 1 mod p^e into g^(phi(p^e)) = 1 mod 2p^e but my brain is dead and i cant see how

reeeeee this is driving me crazy i feel stupid

<@&286206848099549185>

[sacred junco]

mod 2p^e only depends on mod 2 and mod p^e since p^e and 2 are relatively prime

[wise oyster]

im not sure i see why that helps

in regular circumstances maybe i would but my brain has melted from 7h straight of number theory

wait i think i mightve just seen something

is p^e + 2 coprime to 2p^e? If so then ive got it

it probably is lemme see...

right the prime factors of 2p^e are 2 and p while the prime factors of p^e + 2 do not include 2 or p since p is odd

aight got it

wait no

nvm yes

got it

lol

now to figure out the even case

i dont even know what they mean by add p^e to it

[wise oyster]

aight i need to take a break and sleep but id really appreciate it if anyone could shed some clarity on this odd even argument to get the primitive roots mod 2p^e... Ill read it in the morning if anyone responds

i understand the rest of the proof (thank fuck) this part is the only part holding me back

[silk vine]

Prove that for any given irrational number $u$, there are infinitely many rational numbers $\frac{p}{q}, p,q \in \mathbb{Z}$, such that $\abs{ u - \frac{p}{q}} < \frac{1}{q^{2}}$

[sterile pumice]

MisterSystem

[silk vine]

I really don't want to the full proof of this problem

Just to discuss ideas of how to solve it.

I'm supposed to prove it using the pigeonhole principle

One thing to notice is that it's always possible to find rational numbers p/q such that the absolute value of the difference u-(p/q) is less than or equal to 1.

Ofc

Just take p\q = floor(u)

So without loss of generality, we can suppose we will suppose |u - (p/q)| < 1

I guess that's the first thing to do

Now, 1/q² divides the interval [0,1) into q² pieces

In the sense that $[0,1) = \bigcup\limits_{k=1}^{q^{2}} [\frac{k-1}{q^{2}}, \frac{k}{q^{2}})$

[sterile pumice]

MisterSystem

[silk vine]

Sorry for the bad typesetting

But I think you get what I mean

These are all disjoint

So these can be our "pigeonholes"

But I really don't see how to keep up with the proof

Maybe I should give a proof by contradiction? I don't really see how could I construct all these infinitely many rational numbers.

Looking for a proof by contradiction seems more natural.

[silk vine]

Aaaaah

Ok so now I know how to solve it.

Can I post the proof here?

[torn escarp]

sure

[silk vine]

Ok, it's actually wrong.

I have no idea then

[jaunty thunder]

œ

am i too late

noted

[silk vine]

I'm not sure what to do next really

I guess something natural to prove is this

for any given q

there always exists a p<q^2 with |u-(p/q)| < 1/q^2

so that the pigeonhole principle would naturally fit in this proof

this is a conjecture of course and a much stronger statement than the one I'm trying to prove

but I really don't know what to do

could you give me some tips of what to do next?

[silk vine]

I don't really see where we getting at

But I'll keep that in mind

[wise oyster]

@keen furnace my main problem with that is that i was only able to show that g^phi(2p^e) = 1 mod 2p^e when g is odd, not that phi(2p^e) was in fact the order of g mod 2p^e... and if i add p^e to g id first have to show that g+p^e is also a primitive root mod p^e right? (Though I think I see how that could be done)

[wise oyster]

alright so correct me if im wrong but is this a good argument for the odd case:

$g^{\phi(p^e)}\equiv 1 \mod 2 => p^e\cdot g^{\phi(p^e)}\equiv p^e \mod 2p^e$. Similarly $g^{\phi(p^e)}\equiv 1 \mod p^e => 2\cdot g^{\phi(p^e)}\equiv 2 \mod 2p^e$. Adding the two gets us $g^{\phi(p^e)}(p^e+2)\equiv p^e + 2 \mod 2p^e$ and so $g^{\phi(p^e)}\equiv 1 \mod 2p^e$ because $gcd(p^e + 2, 2p^e) = 1$. This shows that $ord_{2p^e}(g) | \phi(p^e) = \phi(2p^e)$. Conversely, if $g^k \equiv 1 \mod 2p^e$ then $g^k \equiv 1 \mod p^e$ and so $ord_{p^e}(g) = \phi(p^e) | k$. So the smallest value of k possible is $\phi(p^e)$ and we know that that value works so the proof that g is a primitive root $\mod 2p^e$ if g is odd and a primitive root $\mod p^e$ is complete