elementary-number-theory

[wispy creek]

i saw the group theoretic proof once

[leaden swan]

Because it's more efficient

[wispy creek]

for any group G and an element a of G. a^|G| = e ?

[leaden swan]

Yes

[wispy creek]

welp that eulers theorem then

with G = (Z/n)*

group theory too op

anyways thnx for the help. ill get back to the book

[bleak edge]

Still don't know if arithmetic function stuff belongs here or in #advanced-number-theory, but is there a relation between $DGF(a_n)$ and $DGF(a_{n-1})$? Alternatively, a way to convert from DGFs to OGFs would help, because the transformation is trivial on ordinary generating functions.

I've tried using this formula (https://en.wikipedia.org/wiki/Generating_function_transformation#Polylogarithm_series_transformations) to convert, but it seems that is only practical in one direction.

[sterile pumice]

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

[torn escarp]

if your function is multiplicative you can imagine the euler factorization breaking it up to an OGF on every prime

I don't think there's a clean relationship between a_n and a_{n-1} because you're mixing multiplication and addition

[sacred junco]

Well, I'm here

What are p-adic numbers?

I'll do my best to understand

[torn escarp]

do you know about modular arithmetic, like the chinese remainder theorem?

[sacred junco]

Nope

Nothing

Is something related to the "mod"?

Where I was at hs I sometimes searching about math (divulgation) I saw something like "5 mod 6"

Or something like that

[torn escarp]

yeah, I guess it's sort of hard to explain without having some experience with some basic number theory problems first

yeah, 5 mod 6 sorta stuff is sort of the starting point

[sacred junco]

Okay, so I guess it's better to first have more math knowledge before getting into that

[torn escarp]

yeah, like know a little bit like fermat's little theorem and just a little bit of time playing around with congruences, solving linear diophantine equations can't hurt

[sacred junco]

Okay

So that's like in Pokémon when you try accessing the league without medals. First I need the 8 medals

[torn escarp]

one of the first things that steps you in the direction of p-adics is learning hensel's lemma which is about solving congruences mod p^n

lol

yeah exactly like that

[sacred junco]

Well, let's just leave it for now. I must study first calculus because it's like the key to the rest of math

[torn escarp]

it turns out hensel's lemma is really newton's method from calculus

so you might be learning that normally, so don't forget about that one

[sacred junco]

Okay

[bleak edge]

Unfortunately it's not multiplicative. I was seeing if I could do anything interesting with the Dirichlet series of Mandelbrot orbits, but I guess Dirichlet series don't behave well with recursively defined sequences.

[torn escarp]

yeah, the recursion has to be done in a way that's relating to terms based on multiplication, not addition basically

but among powers of a prime, multiplication is just addition in the exponent, so it does look like an ordinary power series that way, but going n to n-1 breaks prime factorization so no go

[bleak edge]

I wonder if taking the exponential would work though, then addition becomes multiplication

[torn escarp]

if you want to relate a_n and a_{n-1} as coefficients on an ordinary generating function or exponential generating function, that's simple

no idea what you're really doing, I'd recommend looking at https://www2.math.upenn.edu/~wilf/gfology2.pdf

[bleak edge]

yeah, I've done that, but I get integral equations and I don't know what to do with those

[torn escarp]

I've said as much as I can without seeing the actual problem itself I'm afraid lol

[bleak edge]

There isn't much of an actual problem, I'm just messing around with symbols. Just seeing if there's any interesting generating functions of the sequence z_n = z_{n-1}^2+z_0.

[torn escarp]

gotcha, well sounds fun

[opal falcon]

how to get this?

[tacit peak]

number theory go hard

[urban peak]

Im trying to show that $g(x)=\lfloor x \rfloor +\lfloor x+\frac{1}{N}\rfloor +\lfloor x + \frac{2}{N} \rfloor + \ldots + \lfloor x+ \frac{N-1}{N} \rfloor=\lfloor Nx \rfloor$ is equal to $\lfoor Nx \rfloor$ via induction but Im having some trouble

[sterile pumice]

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

[urban peak]

for base case $N=1$, I get the sum of x's + integers which isnt equal to floor(1x)=x

[sterile pumice]

kingphilip77

[iron surge]

I think that statement you’re trying to prove is false since as you pointed out, the base case doesn’t hold. Also the floor of x is x precisely when x is an integer

@urban peak

[urban peak]

I am fairly certain it holds, instructor basically told us that

i must be doing something wrong

am i inducting on the wrong variable?

[iron surge]

Hmm, well if this is supposed to be true for all Natural N, you just showed that’s false. Where exactly do each of the variables live?

[urban peak]

integers

x is any real number actually

even if i fix N=1, and do base case for x=1, i get 1+2+3+...+1 = 1(1)

which is not true

[edgy nimbus]

you're wrong here

for N=1 and x=1 you get 1 + 2 = 3

its the sum of n+1 terms, not x terms

but yes, the statement is false, at least if its for all n in N and all x in R

I have to find an expression for S_2 and S_3 using elementary symmetric polynomials
https://cdn.discordapp.com/attachments/373217754666500097/862055632009560064/unknown.png
cant quite find a way to prove my answer even tho the result is pretty intuitive
using this notation, S_2 would obviously be e_1² - 2e_2 and S_3 would be e_1^3 - 3e^2e_1 + ne_3
https://cdn.discordapp.com/attachments/373217754666500097/862056402146295809/unknown.png
but i'm not sure how I can prove it

[urban peak]

its all $N \geq 1$ and x reals

[sterile pumice]

kingphilip77

[urban peak]

but i see what u mean for my base case

ill try again

[iron surge]

@urban peak this statement is false and another person other than me has confirmed its false. Since x is supposed to be an arbitrary real number, and you can’t induct on x. You must induct on N, but again that statement you’re trying to prove is false

[urban peak]

hm that is odd. what would the sum be equal to then?

[iron surge]

@urban peak that is a good question that I’m interested in knowing the answer to. Unfortunately I don’t know what that sum would equal. It’s possible that that equation holds for sufficiently large N, but that’s just a guess

[urban peak]

ok thanks ill lyk if i find anything more

[iron surge]

@urban peak You're welcome; awesome thanks!

[copper canyon]

How do I approach this question?
x^(25)=2mod(133)

[wooden crater]

133 = 19 x 7 just to save some time for anybody else. also why tf is 133 not prime that’s gross

[leaden swan]

Solve the simultaneous system x^25=2 mod 7 and x^25=2 mod 19

[wooden crater]

why just x = 2 mod 19?

[leaden swan]

mb

x^6=1 mod 7 for any x

So x=2 mod 7

x^18=1 mod 19 for any x

Does anyone here have a program which does extended Euclidean algorithm ?

The idea is to compute a and b such that x^(25a)=2^a and x^(25a+18b)=x=2^a

Where 25a+18b=1

[wooden crater]

there’s gotta be a simpler solution than resorting to a program for this

[leaden swan]

I mean the Euclidean algorithm is easy to execute

I am just being lazy

[wooden crater]

o

[leaden swan]

Anyway you use CRT to combine those 2 congruencies

And get your solution

@copper canyon

[leaden swan]

You get a=-5 , which means
x=2^-5 mod 19=(10)^5 mod 19=3 mod 19

So your system is x=2 mod 7 and 3 mod 19

[wooden crater]

well now what

[leaden swan]

Now just CRT and you are done

x=2(19)(3)+3(7)(11) mod 133

x=345 mod 133
x=79 mod 133

[sterile pumice]

*-*

[heady basalt]

The smallest number divisible by a_1 through a_n, is in particular divisible by a_n and by the smallest number divisible by a_1 through a_(n-1) (precisely because it is divisible by a_1 through a_(n-1))

Each problem has multiple facets

Some make it trivial is all

[torn escarp]

prime way is not too bad either since you're effectively looking at max(a,b,c)=max(max(a,b),c)

[heady basalt]

yeah, works too

[cloud oracle]

What about for gcd? Is $$gcd(a_1, a_2, \ldots, a_n) = gcd(gcd(a_1, a2, \ldots, a{n-1}), a_n)$$

[sterile pumice]

RisenSteam

[heady basalt]

The largest number that divides a_1 through a_n, in particular divides a_n and the largest number that divides a_1 through a_(n-1) (precisely because it divides a_1 through a_(n-1))

Likewise, if you look at it from the prime factor standpoint, we're saying that min(a,b,c)=min(min(a,b),c)

[cloud oracle]

So yes? Sorry, i am quite new to number theory!

[heady basalt]

yup

[cloud oracle]

thank you

[weary gate]

https://pastebin.com/CXErhwBR

[sleek cove]

pls

[stiff verge]

Yes

[fiery zenith]

https://i.imgur.com/eN24dba.png
https://i.imgur.com/gncESsR.png

Why is this proof so... complicated

It just feels proving this is cyclic should be simple 🤔

[sterile pumice]

Shuri2060

[urban peak]

can Fermats little theorem be used to show a number is prime? i was under impression that it didn't work in that way, only could tell us if a number was composite

[haughty lichen]

no it can't

[urban peak]

awesome. are there any elementary tests like korselt criterion or rabin miller test that would tell me if a number was prime?

think that its same case as flt, they can only show if a number is compsoite

[haughty lichen]

no

[urban peak]

but FLT, korselt criterion, and Rabin Miller all can show a number IS composite right?

[haughty lichen]

try googling (fermat)-pseudoprime, Mersenne prime and so on

[urban peak]

im familar with those, im just making sure my understanding of the purpose of the test is correct

[haughty lichen]

the purpose is that if it passes a lot of those tests then it is likely a prime

[urban peak]

but indepdently, those tests can only confirm that a number is composite?

[haughty lichen]

yes because there exists numbers such as these

hence the theorems aren't if and only if

[urban peak]

gotcha thanks

[sacred junco]

For what values mod a do all integers have a cubic root mod a?

All primes? Multiples of 3?

[weary gate]

https://pastebin.com/k1Dkdi37

[inner anchor]

where did the mute go

[weary gate]

hmm

[devout furnace]

I think you’re referring to the fermat primality test which is probabilistic

so you can’t use it to say a number p is prime for certain, but it can say it is “probably” prime

but there’s plenty of “fermat pseudoprimes” which pass the fermat primality test but aren’t actually prime

hence why it’s a probabilistic test and not deterministic

[sleek cove]

he changed his name rip lithium

[sacred junco]

How to show $a^{\varphi(b)}+b^{\varphi(a)} = 1 \mod ab$ whenever $\gcd(a,b)=1$?

[sterile pumice]

Carla_

[sacred junco]

Can use Euler theorem to see a^phi(b) = 1 mod b and b^phi(a) = 1 mod a, but how to go from there?

[iron surge]

@sacred junco I got you

[sacred junco]

you got me?

[iron surge]

yup so since $(a,b)=1$,...

[sterile pumice]

logician_pdx

[iron surge]

we have $b|a^{\varphi(b)}-1+b^{\varphi(a)}$ and $a|a^{\varphi(b)}-1+b^{\varphi(a)}$, so $ab|a^{\varphi(b)}-1+b^{\varphi(a)}$. By the definition of congruence, we conclude $a^{\varphi(b)}-1+b^{\varphi(a)}\equiv1\pmod{ab}$

[sterile pumice]

logician_pdx

[iron surge]

I skipped a tiny detail, but hopefully you see that $b|b^{\varphi(b)}$ and $a|a^{\varphi(b)}$.

[sterile pumice]

logician_pdx

[iron surge]

we also had $b|a^{\varphi(b)}-1$, so $b|a^{\varphi(b)}-1+b^{\varphi(b)}$

[sterile pumice]

logician_pdx

[iron surge]

and similarly, for $a$

[sterile pumice]

logician_pdx

[iron surge]

make sense @sacred junco ?

[sacred junco]

yea its basically what i did

[iron surge]

nice!

so you got it

[sacred junco]

cuz totient funcrion geq 1

[iron surge]

yup

this is because 1 is always relatively prime to any integer

[sacred junco]

probably can generalize this

to finitely many integers

not sure

[torn escarp]

definitely

you can get a very explicit way of writing down solutions you've solved for each mod p^n and combine them together

[sacred junco]

mod p^n?

[torn escarp]

right, if you're trying to solve something mod N you can factor N into its powers of primes, those are the smallest relatively prime things you can make

[sacred junco]

yea

[iron surge]

this one has a typo,..

[iron surge]

this one does too.

we have $b|a^{\varphi(b)}-1+b^{\varphi(a)}$ and $a|a^{\varphi(b)}-1+b^{\varphi(a)}$, so $ab|a^{\varphi(b)}-1+b^{\varphi(a)}$. By the definition of congruence, we conclude $a^{\varphi(b)}-1+b^{\varphi(a)}\equiv1\pmod{ab}$

[sterile pumice]

logician_pdx

[iron surge]

This is the corrected version @sacred junco

The typo I had was $b^{\varphi(b)}$ instead of $b^{\varphi(a)}$

[sterile pumice]

logician_pdx

[sacred junco]

yea i didnt even notice lol its okay

[iron surge]

yea, the logic is still the same tho

[sacred junco]

i just wanted to check if what i did was right so i asked as if i didnt solve it, not to bias someone who answers

[iron surge]

okay be careful when you do that tho, because we don't like to give answers right off the bat if no work is shown
but since you told me about what a and b each divide, I could tell you thought about this problem already
so I answered.

[sacred junco]

yes im aware thats why i said that xD

[torn escarp]

you could say this is the chinese remainder theorem

[sacred junco]

yea i was getting chinese reminder vibes :o

[cloud oracle]

Miller Rabin is a probabilistic test. If you run enough rounds of the MR with different prospective witness numbers, none of who confirm that the number is a composite, then there is a very high degree of probability that the number is a prime.

All Composites don't have a Fermat's witness - Carmichael numbers don't have a Fermat's witness even though they are composite. However all composite numbers have multiple Miller Rabin witness for Compositeness. So if you run MR with multiple prospective witnesses, the probability that the number is a composite without being confirmed by your rounds is ignorably small.

There are also deterministic tests for Primality. The AKS tests is deterministic test which runs in polynomial time and also doesn't use any unproven conjectures like the Reimann Hypothesis. There are also other deterministic tests which use Reimann & check primality in a deterministic way.

[wispy creek]

how tho ?

i get one direction how x = 1 mod(12) -> x = 1 mod(2, 3, 4 and 6)

but how do i show the other direction

[devout furnace]

equivalently you already showed the expression is 1 mod a and 1 mod b so by (a form of) chinese remainder theorem since (a, b) = 1 we have the expression is 1 mod ab

in general, if you’re trying to find something mod a_1 * a_2 * … * a_n, where the a_i are pairwise coprime, you can consider the solution to the system of individual congruences mod a_1, mod a_2, …, mod a_n

[leaden swan]

x=1 mod 4 implies x=4k+1
x=1 mod 3 implies x=3l+1
This implies 4k=3l or 4k=12m for some m,i.e., x=12m+1

[devout furnace]

and this again is due to the chinese remainder theorem

[leaden swan]

You don't need the other 2 congruencies

[wispy creek]

v clever

[wispy creek]

dooesnt chinese remainder theorem only guarantee a solution to 2 congruence systems ?

[devout furnace]

it can be extended

[leaden swan]

Or you can use this

[wispy creek]

does it extend to a stronger version of "only guarantees the existence of a solution"

[devout furnace]

the theorem always shows existence

it’s up to you to find a construction

[wispy creek]

ic

[devout furnace]

actually what have I been saying this whole time

[wispy creek]

can u link me the proof of this ?

im not sure how to use CRT here

and this sounds hella useful

[devout furnace]

you don’t need anything fancy to show that 1 mod a and 1 mod b implies 1 mod ab for (a, b) = 1

crt just shows existence

which here isn’t very useful

[leaden swan]

Do induction on this

Suppose you have x=c_1 mod a_1 ,c_2 mod a_2 and c_3 mod a_3 first find y: x=y mod a_1 a_2

Then use that to find z such that x=z mod a_1 a_2 a_3

[devout furnace]

oh right, the point is of the unique existence of a solution

[devout furnace]

so here you can say that 1 is the only solution

[wispy creek]

oof im confused as hecc

can we do a simple example of CRT real quick

[leaden swan]

say x=2 mod 3 ,1 mod 2 and 4 mod 5

Is that ok

[wispy creek]

ye

[leaden swan]

Then this is equivalent to x=2(2)(2)+1(3)(3) mod 6, x=4 mod 5

x=5 mod 6,x=4 mod 5

Which is equivalent to x=5(5)(5)+4(6)(1) mod 30

x=29 mod 30

[wispy creek]

yeah ok makes sense

[devout furnace]

I think it’s worth emphasizing that CRT isn’t the actual algorithm used to construct the solution, rather it’s something which lets you choose two congruences whose modulo are relatively prime and combine them into one

[leaden swan]

It tells you you can do that

It doesn't give you a way to do it

[wispy creek]

in the ss example, 2, 3, 4, 6 are not pairwise coprime. how are they combining those

[devout furnace]

apply CRT one step at a time

first combine 2 and 3 because they’re relatively prime so CRT applies

[wispy creek]

aight lets say i apply it to mod 2 and mod 3, get a solution mod 6

but then 4 and 6 are not coprime

[devout furnace]

hmm

[leaden swan]

You can show x=a mod (2^2)(3) is completely determined by b and c where x=b mod(2^2) and x=c mod 3

[wispy creek]

true

[leaden swan]

Other congruencies are just extra material you check at the end

As in "does the final solution satisfy those conditions"

If not,there is no solution

If yes,There is a solution

[wispy creek]

this this true that "x = a mod m is equivalent to solution to the system x = a mod (all the divisor of m)"

[leaden swan]

Should be

x=mk+a implies x=d(nk)+a where m=dn

[wispy creek]

yeah one direction is simple enough but the other direction im not sure how to show

[devout furnace]

prime divisors I think

well actually something like mod 36 might be weird

[wispy creek]

thonkery

[wispy creek]

i just tried out ur thing to prove a system of n congruences has a solution and it was goddamn genius

[torn escarp]

here's a way to explicitly construct a solution from the solutions mod the relatively prime numbers as an example $$x=x_a (bc)^{\varphi(a)}+x_b(ac)^{\varphi(b)} +x_c(ab)^{\varphi(c)} \mod abc$$

[sterile pumice]

Merosity

[torn escarp]

you can see how for instance (bc)^phi(a) is 1 mod a and 0 mod b and mod c, so you're easily selecting out

but the exponent can be kinda gross, it's just nice to have

[wispy creek]

dang thats pretty nice too

but yea not a fan of those exponents

[sterile pumice]

soαρ

[wispy creek]

^ ignore this

found the ans

[sleek cove]

dont tell me what to do

[wispy creek]

stop telling me not to tell u what to do

[wispy creek]

not sure how to do (c)

something something expected values ?

like given an integer n between 1 and x, the probability of n and n + 2 being prime is 1/ln^2(x). we sum up all the probabilities ranging n from 1 to x to get a total probability of x/ln^2(x) ?

but then thats the probability. the number of twin primes is x^2/ln^2(x) ?

havent done much probability

[inner anchor]

first find what the probability for some a to be a prime is, and then consider a and a+2 being primes as independent events

[wispy creek]

probability of a being prime is 1/ln(x). so a and a+2 being prime has the probability of 1/ln^2(x) ?

[inner anchor]

yes

just mulitply the probabilities

[wispy creek]

wow

[inner anchor]

this is a pretty bad bound though

[wispy creek]

so the total number of twin primes = probability * x

gg ?

[inner anchor]

yeah

[wispy creek]

[inner anchor]

lol

[wispy creek]

holy shit that was too simple

[inner anchor]

troll problem

i hope i havent made some stupid lapse in judgement

but it seems fine to me

[sleek cove]

its missing a constant

[urban peak]

im trying to prove that for an odd integer k>1, there are infinitely many primes p such that at least of the intgers from 1 to p-1 has no kth root modp

not really sure how i am supposed to proceed

[prime sparrow]

Well if p=ak+1 for some k, do you see why there will be an integer with no kth root mod p?

[urban peak]

why not? seems like it should work

[prime sparrow]

What do you mean by why not? Are you saying that all integers will have a kth root mod p?

Also here is a hint: the multiplicative group of Fp is isomorphic to Z/(p-1)Z

[urban peak]

im saying it seems like all intgers do in fact have a kth root mod p, but i guess there is not and there is flaw in my logic. im not familar with much group theory so hint doesnt help much 😦

[prime sparrow]

This question (or atleast the way I’m solving it) seems a little too difficult then

[urban peak]

hm i guess ill just keep trying then

[prime sparrow]

For an example of what I was saying, when k=3 look at p=7, you can then check that 2 has no cube root mod 7

[urban peak]

makes sense but generalizing and proceeding seems difficult

[prime sparrow]

Yes the generalisation is pretty hard: here is a fact that will help (it is hard to prove but take this for granted) for every prime p, there is an integer k<=p-1 such that the powers of k give you all nonzero remainders modulo p, and k^(p-1)is congruent to 1 mod p.

I realize I’ve used k for the integer here, this k has nothing to do with the k in the problem, sorry

[urban peak]

is this a named theorem or just a general result? would like to look into it more if i can find something on it

[torn escarp]

sounds like fermat's little theorem

[urban peak]

think you're right didnt even realize

[prime sparrow]

It is called the primitive element theorem

It is a bit harder than fermat’s little theorem

[urban peak]

it looks like i need basic group theory just from searching it up. think i might need to take a min and just get some group theory basics since it seems anything remotely complex in nt needs it

[prime sparrow]

Oh wait that is a different theorem, I don’t know of a name for this theorem, but it isn’t fermat’s little theorem

[inner anchor]

Its just the existence of a primitive root

[prime sparrow]

Yes

[sacred junco]

@wispy creek wht book is this? silverman?

[wispy creek]

yes

[hot pond]

can some help with q3?

[inner anchor]

probably if you posted your problem

[hot pond]

lol, it was in question3 chat

[copper canyon]

How do I solve this?
I keep getting wrong answers

[torn escarp]

show your work so far

I'll walk through the answer here in a bit if you're still struggling cause it's pretty straight forward once you know

[copper canyon]

x = 24^101 mod 25
x = 24^101 mod 4

x = (-1)^101 mod 25
x = 0^101 mod 4

x = -1 mod 25
x = 0 mod 4

x = 4t
4t = -1 mod 25
//gcd(25,4) == 1 than
4t = t = -1 mod 25
t = -1 + 25v

x = 4(-1 +25v)
x = -4 + 100v
x = 96 + 100v
x = 96 mod 100

[torn escarp]

just a general tip, it's usually easier to start with the big one and go smaller

like do x=-1+25t and then look at it mod 4

but I'll keep checking your work, just got to this part

this step is wrong:
4t = t = -1 mod 25
t = -1 + 25v

4t is not t mod 25

4t=-1 mod 25 you need to find and multiply by 4^-1 on both sides

this is why starting from the bigger one is easier, since the inversion you'd end up having to do would be mod 4

only good way I see to do that here is by hensel lifting, which is just extra work that we should avoid, I can show you how to do that

basically we solve 4u=1 mod 5, then use this to solve 4u=1 mod 25

mod 5 is easy, u=4 will work

so now mod 25 we use u=4+5v and we have 4(4+5v)=1 mod 25

you can rearrange this all out to get 5*(3+v)=0 mod 25

so really we're just back down to looking at 3+v=0 mod 5

so v=2

and that determines it, u=4+5*2 = 14

oh whoops forgot to distribute the 4

5*(3+4v)=0 mod 25 becomes 3+v4=0 mod 5 and so v=3

so u=19

[copper canyon]

so x ends up 76?

[torn escarp]

hmm 74 actually but that's not right either haha

do it the other way, it's more direct, I'll check my work again, I already made a mistake while working it out so probably there's another

[copper canyon]

Yeah. If it wasn't the course has a test, I would just write a code to my math library and forget about it 😄

[torn escarp]

oh u is just the inverse of 4

so when you multiply both sides by it I get t=-19

[copper canyon]

ohhh

Now that makes perfect sense

where was the mistake?

[torn escarp]

I just forgot what I was doing after working out the inverse

[torn escarp]

everything from here on down is just working out what 4t=-1 mod 25 is

you solved for t incorrectly

you need to multiply by 4^-1 on both sides

I worked out that 4^-1 = 19 so multiplying by it I get t = -19 mod 25

or I could just put t=6 since it's smaller

so x=4*6 = 24 mod 100

like I said though this is the bad way to do it

you should start from x=-1+25t mod 4

0=-1 + t mod 4 means t=1 mod 4 and so we get x=-1+25=24 mod 100 immediately

even if 25 turned out to be something else other than 1 mod 4, inverting it would still be very easy since it can only really be 3

[wispy creek]

cough method of successive squaring cough

[torn escarp]

I'll take hensel lifting any day thanks haha

to be fair, doing either of these by hand is a pain in the ass lol

[wispy creek]

what even hensel lifting

[hardy kayak]

heyy, I was stdying substitution cipher,I had a doubt in it. can anyone help me with it

[torn escarp]

in the simplest case, you can turn solving for something mod p^n into solving basically the same problem mod p, but n times

so for instance 4x=1 mod 5^2 I solved it mod 5 first to get x=4

then I plugged in x=4+5y to get 4*(4+5y)=1 mod 5^2 but it simplifies to become 5(3+4y)=0 mod 5^2

since we already have 5 there, we know to make 0 we are just solving 3+4y=0 mod 5 now

so that's the second time solving a problem mod 5, and this trick generalizes

[wispy creek]

nice trick

r u guaranteed to get smth like 5*smth = 0 mod 5^2 ?

[torn escarp]

yeah, so we can go a little more general to show it easier maybe

let's say f(x)=4x-1=0 is what we want to solve mod p^n

then if we can solve f(x)=0 mod p, we can use this to get the next power up, let's go a bit more general and say f is a polynomial

then the next step will be $f(x+py)=0 \mod p^2$ is what we want to solve

[sterile pumice]

Merosity

[torn escarp]

we have x already determined mod p, so we just need to determine y mod p, think of it as determining the base p expansion of the number one digit at a time

so if we expand out the polynomial now, $$f(x+py) = \sum_{k=0}^n a_k (x+py)^k = \sum_{k=0}^n a_k (x^k +k py x^{k-1}) \mod p^2$$

[sterile pumice]

Merosity

[torn escarp]

notice all the higher terms in the binomial expansion die out cause they are p^2 or higher

if you look at that and expand it out, it simplifies down to:

$$f(x+py) = f(x)+py f'(x) \mod p^2$$

[sterile pumice]

Merosity

[torn escarp]

you with me so far? kind of getting weird lol

[wispy creek]

oh shit forgot to check. im back

[torn escarp]

happens to me too lol

[wispy creek]

ok yeah i followed it so far

took me like 5 tries but i got there

not sure why the next step is to look at f(x + py) tho

seemed kinda arbitrary

[torn escarp]

yeah, it's cause we solved f(x)=0 mod p

and since py=0 mod p, we're basically blind to it

mod p^2 that's just the amount we have to add on to take our solution mod p and fix it up to work mod p^2

[wispy creek]

kk makes sense

[torn escarp]

I can explain that a bit more later, but I'll keep going from here now @wispy creek

[wispy creek]

aight

tfw derivatives in NT

[torn escarp]

So we're wanting to solve f(x+py)=0 mod p^2 and all we need to do is determine y, since we know x, so this becomes

$0=f(x)+py f'(x) \mod p^2$

[sterile pumice]

Merosity

[torn escarp]

yeah weird haha 😛

we already know f(x)=0 mod p so it's safe to divide this by p

$$0 = p( \frac{f(x)}{p} + y f'(x)) \mod p^2$$

[sterile pumice]

Merosity

[torn escarp]

since p*(stuff)=0 mod p^2 we know the (stuff)=0 mod p

$$0 = \frac{f(x)}{p} +yf'(x) \mod p$$

[sterile pumice]

Merosity

[wispy creek]

oh shit

[torn escarp]

as long as $f'(x) \ne 0 \mod p$ we can now solve for y exactly

[sterile pumice]

Merosity

[torn escarp]

$y= \frac{-f(x)}{p f'(x)}} \mod p$

[sterile pumice]

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

[torn escarp]

so our new answer is $x+py = x-\frac{f(x)}{f'(x)}$

[sterile pumice]

Merosity

[torn escarp]

it turns out this will always be how the step works to get new digits

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$

[sterile pumice]

Merosity

[wispy creek]

wtf this looks like newtons method

[torn escarp]

it is newton's method 😛

[wispy creek]

[torn escarp]

but how you measure distances between numbers is different in this topology, so this is how you do newton's method in the p-adics

so maybe try to prove the general thing now

[wispy creek]

aight throw the general statement at me, ill try to prove it

[torn escarp]

so take your base case as $f(x_1)=0 \mod p$ and $f'(x_1) \not =0 \mod p$ and then use this to show that if you have $f(x_n)=0 \mod p^n$ then there's a unique solution to $f(x_{n+1})=0 \mod p^{n+1}$

[sterile pumice]

Merosity

[torn escarp]

let me be a bit clear about what I mean with an example

like earlier we wanted to solve f(x)=4x-1=0 mod 5

so if I solve this, with x=4 and then evaluate f'(4) and show this is nonzero mod 5, then this means my base case is satisfied

and I'm guaranteed I can always solve f(x)=0 mod 5^n by repeatedly stepping one digit in base 5 at a time

[wispy creek]

aight ill try to prove it and when i come back lets talk about this "base p" thingy

[torn escarp]

sure, we can work some in base 10 or base 2, it might be easier

or maybe just try to work out a concrete example like

solve x^2+1=0 mod 5^4 to get a feel for it

that's kind of an interesting one because as you solve x^2+1=0 mod 5^n as n gets larger, you're computing digits of an irrational number in the 5-adics that we could call i

[wispy creek]

actually how is it safe to divide by p ?

gcd(p^2, p) = p != 1

so the inverse doesnt exist mod p^2

[torn escarp]

yeah, however as an integer if we're looking at f(x)=0 mod p

this means f(x)=pm for some m

so f(x)/p = m is perfectly well defined as an integer

so we're sort of shifting perspective a bit when we write that, so it's a bit tricky @wispy creek

[wispy creek]

ic

what about being able to divide by f'(x)

[torn escarp]

well that's just ordinary modular arithmetic

f'(x) != 0 mod p means it has an inverse

[wispy creek]

oh shit yeah

maketh sense

[torn escarp]

yeah, actually hensel's lemma is more general than what I've said too, but I didn't wanna overwhelm with details

if f'(x)=0 mod p you can still do hensel lifting, just requires your base case to involve working more, like solving f(x)=0 mod p^k for some k that depends on what power of p divides f'(x)

in terms of the p-adic absolute value it's easy to write down, |f(x)|<|f'(x)|^2 is the sufficient condition for x to lift to a unique solution

[wispy creek]

yea ic why u avoided details. good call

[torn escarp]

we could even go more general and talk about the version of hensel's lemma that's actually about polynomials

factorization of polynomials mod p lifts to factorizations mod p^n lol

[wispy creek]

just to check, what im trying to prove is, if f(x) = has a solution mod p, it has solution mod p^n for any n >= 1?

[torn escarp]

yeah, and the way to do that is by induction on n

[wispy creek]

oh ok that makes a lot more sense then

[torn escarp]

also you assume f'(x) !=0 mod p as well

[wispy creek]

kk

[wispy creek]

@torn escarp ive been trying to prove this for a while now. i was able to show x_{n+1} is a solution mod p^(k+1) given that x_n is a solution mod p^k. but got stuck on the uniqueness part

heres an example that seemingly contradicts uniqueness

f(x) = x^3 - 1

f(x) = 0 mod 3 has a solution x = 1

but f(x) = 0 mod 3^2 has 2 (or maybe more) solutions x = 1 and 4

[torn escarp]

yeah good question

it's unique once you fix x for the base case

the further digits you add on to whatever choice you make there are what is unique

and the uniqueness will pop out of the fact that f'(x) != 0 mod p will allow you to solve for the next digit exactly

like we did in that example mod p^2 that I showed earlier in reducing it to mod p

[wispy creek]

r u saying once we fix x_n, x_{n+1} is fixed and therefore unique ?

[torn escarp]

yeah

exactly

[wispy creek]

oh

cool

i think i get it then

[torn escarp]

nice 😎

[wispy creek]

thank you for enlightening me mero

[torn escarp]

yeah you're welcome 😛

p-adic stuff aside this is good to have just for regular modular arithmetic problems

if you're trying to solve something mod n, the chinese remainder theorem only lets you split it into solving congruences modulo relatively prime numbers, which means distinct powers of primes

[wispy creek]

then i use hensel lifting to solve mod p^n

[torn escarp]

this thing you're proving now, hensel's lemma, lets you solve things mod p which is easier and then lift up to that

bingo

sniped me lol

[wispy creek]

v useful

[torn escarp]

yeah, pretty fun when calculus starts to pop up in number theory stuff lol

[wispy creek]

n - 1

$(n-1)^2 = n^2 - 2n + 1 \equiv 1 (mod n)$

[sterile pumice]

soαρ

[wispy creek]

does this count as trivial ?

@sacred junco

[inner anchor]

Thats just (-1)^2 = 1 mod n

Which is trivial yes

[wispy creek]

dang

got too ambitious

[proven rune]

How do you solve 2^k -1 ≡ 0 (mod 4599)? I noticed that 4597 is a prime, but not sure if this fact can be exploited.

[inner anchor]

A tedious way is to note that k must divide phi(4599) = 2^5 × 3^4 and then just checking all of the 30 possibilities

Quite a few of those can be eliminated simply by size checks

Lol those were super wrong

[proven rune]

I see. This method should definitely work, but is there a smarter way to deal with the congruence? I think the problem is not intended to involve brute force checking possibilities.

[inner anchor]

crt stuff probably

[proven rune]

Is crt Chinese Remainder thm?

[inner anchor]

Yes

Im not 100% confident on how you combine the solutions due to the exponents being in mod phi(n)

You can probably just combine them directly

[proven rune]

thanks. I'll try the CRT approach and see how it goes!

[inner anchor]

Gl

[red gyro]

# Let p be a positive integer. Consider p (not necessarily) distinct prime numbers
# such that their product is ten times their sum. What are these primes, and
# what is the value of p?

### SETUP ###
# 1) generate primes
#
# REPEAT until success ----->
# 2) check success conditions
# 3) prune responses for complexity

### PROGRAM ###

# Global Variables
primes_array = []


# Methods
def main():
    populatePrimes(2, 12)
    checkSuccess()


def populatePrimes(range_low, range_high):
    for possiblePrime in range(range_low, range_high):
        isPrime = True

        for num in range(2, possiblePrime):
            if possiblePrime % num == 0:
                isPrime = False

        if isPrime:
            primes_array.append(possiblePrime)


def checkSuccess():
    ROC_now = 0  # Rate of Change Now -----> starting value negligible

    for i in range(0, len(primes_array)):
        for j in range(0, len(primes_array)):

            # Rate of change calculation which lowers computational complexity by using the linear design of the
            # problem to prevent excess calculations after surpassing the equality convergence point

            ROC_previous = ROC_now
            ROC_now = 10 * (primes_array[i] + primes_array[j]) / (primes_array[i] * primes_array[j])

            if ROC_previous > 1 and ROC_now < 1:  # ROC_now at success should be 1
                break

            if 10 * (primes_array[i] + primes_array[j]) == (primes_array[i] * primes_array[j]):
                print("***********************Answer: ", primes_array[i], primes_array[j])
            else:
                None
                # uncomment below to see all test cases
                # print("WRONG i:" + str(primes_array[i]), "j:" + str(primes_array[j]) + "    " + str(
                #    10 * (primes_array[i] + primes_array[j])) + " = " + str(primes_array[i] * primes_array[j]))


main() ```

Found a problem where two primes can be found where 10 times their sum is equal to their product

The code runs smoothly but I get to sizes of 100000 max prime range and cant find it

Is there anything blatantly wrong with my method or code?

Adjust range accordingly

[dusk coral]

I don't think there's any solutions with only 2 primes. Since the product is even, 2 must be one of the primes, but then you have 10*(p+2)=2p for the other one.

[red gyro]

I found this problem on a challenge from an institution... that is why I am confused

doesnt make sense, thanks for the help

[torn escarp]

I'm gonna change notation to make n the number of primes since I want to represent primes by $p_i$. We can write this out as $$\prod_{i=1}^n p_i = 10 \sum_{i=1}^n p_i$$ immediately we know two of the primes must be 2 and 5 so pick the last two and divide them out, $$\prod_{i=1}^{n-2}p_i = 7 + \sum_{i=1}^{n-2}p_i$$. Something concrete to work with, next you could consider maybe what happens if one of the primes is 7 or not I guess

[sterile pumice]

Merosity

[torn escarp]

in particular for that other comment, if n=2 then we have 1=7+0 which is a contradiction, consistent with what @dusk coral is saying

my reasoning is slightly different just for 2 primes if we have pq=10(p+q) we necessarily must have p=2 and q=5 for the prime factorization to make sense at all

[red gyro]

I didn't even consider the fact that it could be more than two primes... However it could be only both 1) 2 and not 5 2) 2, 5, and another

but considering I have checked through 2 and 100000 for two primes you are probably right

[torn escarp]

pq=10(p+q) the left side has exactly 2 prime factors and the right side has 2,5,and at least one prime factor in p+q which means it has 3 or more, that's the contradiction I'm going for

[red gyro]

Adjusting my code now, sorry for being thick

[red gyro]

Yep and there it is 2 3 5 5

You can even narrow it down to n>=4 because 10(pi+7) != (2*5)pi

Thanks John and Merosity this was nagging at me

[torn escarp]

👍

[sleek cove]

you're welcome

[copper canyon]

What does this mean?

[leaden swan]

Do you know integers mod 2?

@copper canyon

[copper canyon]

yeah

[leaden swan]

What part do you not get

[copper canyon]

the squigly that looks like equal sign

[leaden swan]

Isomorphism,I think

[copper canyon]

Doesn't that work only if there's a function

f(a)f(b)=f(ab)

?

[leaden swan]

Your function maps 1 to 1

So Z/2Z is {[0],[1]} right?

Z_2 is {0,1}

The isomorphism is map [0] to 0 and [1] to 1

[wispy creek]

wait what

whats the the distinction between Z/2Z and Z_2 ?

is Z_2 just a nice way to represent Z/2Z ?

[leaden swan]

Yes

But some people define Z_2 as the set {0,1} with a+b=(a+b)%2

Practically the same thing

Where a%2 is the least positive reminder

Z/2 has equivalence classes

[wispy creek]

ic

[copper canyon]

z/2z means odd numbers
z_2 means modulo numbers to 2
so z_2 = {0,1}

[copper canyon]

right. But what would be the general definition of isomorphism for groups?

[leaden swan]

f(a)f(b)=f(ab)

[sacred junco]

Z2 and z/2z is same thing

[leaden swan]

f will be your isomorphism

[copper canyon]

f isn't the function?

[leaden swan]

The function is "map [1] to 1 and [0] to 0"

[copper canyon]

ohh

[wispy creek]

z/2z means odd numbers, what ?

[sacred junco]

Its just notation soapy

[copper canyon]

Z is intergers so 2Z doesn't mean even numbers?

[wispy creek]

yeah ik

[sacred junco]

2z is not z_2

[leaden swan]

Sir, Z\2Z is set of odd numbers

[wispy creek]

Z/2Z is Z quotiented out by 2Z

[sacred junco]

Just stop talking about this plssss

[wispy creek]

u stop talking about it first

[sleek cove]

Z|2Z is my favorite set

[upbeat wren]

You like binary digits?

[sleek cove]

i like you

[frank sand]

Does Z/Zp has elements of order two? Is there a nice way to find those elements?

in multiplicative group

[inner anchor]

1 and -1 are the only ones

If p is prime

Also i assume you mean Z/pZ

[frank sand]

yes

okay thank you

[inner anchor]

Simple proof is just that x^2 -1=0 mod p iff (x-1)(x+1) = 0 mod p

[copper canyon]

How do I find x for
5^x = 1 (mod 7)?

[torn escarp]

just want an x that works, or the minimal x?

[copper canyon]

minimal x

[torn escarp]

if you just want one that works, that's easy - that's fermat's little theorem

if you want the minimal, that's pretty much impossible - that's the discrete logarithm problem

you just have to brute force it pretty much

[copper canyon]

minimal interger

Which I think is 6 according to fermats little theorem as you said 🙂 Thanks

[torn escarp]

no

it's 6, but not according to fermat's little theorem

fermat's little theorem gives you 6 which works for every number relatively prime to 7, but it's not the minimal in general

[copper canyon]

huh

I brute forced it seems that 6 is the minimal interger

[upbeat wren]

You only need to test up to (p - 1)/2 for odd p. If there are no repetitions up to then and A^((p-1)/2 is -1 (mod p) you are good.

[inner anchor]

You only need to check the proper divisors of p-1 for a bit of extra optimization

[upbeat wren]

Nice.

[inner anchor]

Very cool yes

[shut echo]

m, n are positive numbers such that 5m +n divides m + 5n.
Prove that m is factor of n.
can someone give a hint?

[leaden swan]

Take m+5n=k(5m+n) and do some shenanigans

[shut echo]

I did that and got m(5k-1)=n(5-k)

[leaden swan]

Oh wait m and n are positive

There is a easier way

5m+n divides (m+5n)+(5m+n)=6(m+n)

Ok,This isn't easier

[shut echo]

5m+n also divides 4n-4m

[shut echo]

or 5(mk-n)=m-nk

wait i think i got it

[leaden swan]

[shut echo]

5m+n divides 24(m+n) and also 24(n-m)

[leaden swan]

5m+n divides 48m

[shut echo]

also 48n

[leaden swan]

Yes

[shut echo]

but doesn't do much ig

[upbeat wren]

Still need this? @shut echo ?

[shut echo]

yea

[upbeat wren]

5km + kn = m + 5n

5m + n <= 5n + m ==> 4m <= 4n ==> m <= n

5km + kn = m + 5n (mod n) ==> (5k - 1)m == 0 (mod n)

5km + kn = m + 5n ==> 0 == (5-k)n (mod m)

m | (5 - k)n and n | (5k - 1)m and I am lost.

I wanna say gcd(5 - k, 5k - 1) = 1 and that helps?

But it isn’t for k = odd so blah.

[leaden swan]

Maybe assume m doesn't divide n and do something with that

[wispy creek]

not really following this line

another q

does this proof work ?

im proving p cannot be written as the sum of 2 squares when p = 3 mod 4

[inner anchor]

Seems alright

You can also just divide both sides by b^2

[wispy creek]

what about the red underlined part tho

[torn escarp]

well this shows a,b aren't in the multiplicative group, but 0 is the only thing not in the multiplicative group so it must be the solution

[wispy creek]

why are a, b not in the multiplicative group ?

dunno much group theory

[torn escarp]

well you just showed that a^2 = -b^2 mod p has no solution when a,b are nonzero mod p

so they must be 0, it's the only option left

[wispy creek]

oh

that was pretty simple

i should just sleep and take a break

[torn escarp]

lol

[wispy creek]

thnx for the help guys

[torn escarp]

you're welcome

[torn escarp]

We can divide out common factors of $m,n$ so without loss of generality we can assume $m,n$ are relatively prime, this turns the problem into proving $m=1$. Since $m+5n \ge 5m+n$ we also know $n \ge m$. Further we can look at $m+5n=k(5m+n) \mod m$ to get $k=5+mt$, plugging $k$ back in we get, $0=24+(5m+n)t$. Since $m,n$ are positive this means $t$ is negative. This restricts what $k,m$ can be to finitely many cases to check.

[sterile pumice]

Merosity

[torn escarp]

lemme know if you run into any issues

[shut echo]

Plugging in k, we get $0 \equiv 24m+5m^2t+mnt \mod m$

[sterile pumice]

Schrödinger's cat

[shut echo]

The RHS is already 0 mod m so why are we dividing by m and then again equating it to 0 @torn escarp

[torn escarp]

don't plug in mod m, just plug in normally

$$m+5n=k(5m+n)$$
$$m+5n=(5+mt)(5m+n)$$
$$m+5n=25m+5n+5m^2t+mtn$$
$$m=25m+5m^2t+mtn$$
$$1=25+5mt+tn$$
$$0=24+(5m+n)t$$

[sterile pumice]

Merosity

[shut echo]

Oh okay

[torn escarp]

since this makes t negative, k=5+mt is a pretty harsh condition since k is also positive, m is going to be small so that when we subtract a multiple of m from 5, it's still positive

[shut echo]

yeah I get it, thanks a lot

[torn escarp]

cool

let me know what you do to finish it, since it seems kind of annoying to finish

[shut echo]

Ig there are only 4 cases
m,k>0 implies t=-1 so (m,n)=(4,4),(3,9)(2,14)(1,19)

t=-2,-3,-4 is also possible

when t=-2, 5m+n=12 so (m,n)=(1,7),(2,2)
t=-3, 5m+n=8, (m,n)=(1,3)
t=-4, 5m+n=6, (m,n)=(1,1)

In all of these m|n so we're done

[torn escarp]

I guess since we only care about when m is not 1, we just need to do t=-2 and m=2

[shut echo]

yeah right

[torn escarp]

kind of weird problem, seems like it'd be easier

seems like it'd be fun to generalize to am+bn being divisible by bm+an with a<b, show that m divides n

[shut echo]

yep

[spark shuttle]

How can i find solutions for $f(x)$ in the congruence $f(x)(x^2-1)\equiv x^2+x-2\pmod{x^3-1}$

[sterile pumice]

ben49

[primal moss]

What have u tried so far

@spark shuttle

[spark shuttle]

just dividing x^2+x-2 by x^2-1 to solve for f, but then theres a remainder term and stuff that I couldnt figure out how to get rid of

[iron surge]

well one place to start might be by noticing that $x^2+x-2=(x+2)(x-1)$ So dividing by $x-1$ gives $f(x)(x+1)\equiv x+2\pmod{x^3-1}$

[sterile pumice]

logician_pdx

[primal moss]

Well, we can’t multiply by the inverse of $x-1$ modulo $x^3-1$ since those are not coprime.

[sterile pumice]

Green4Applez

[primal moss]

But, we can divide everything, including the modulus, by x-1.

So we would get $$f(x)(x+1) \equiv x+2 \pmod{x^2+x+1}$$

[sterile pumice]

Green4Applez

[primal moss]

Then, multiplying by $x$ on both sides gives $$f(x)(x^2+x) \equiv x^2+2x \pmod{x^2+x+1}.$$ Then since $x^2+x \equiv -1 \pmod{x^2+x+1}$, we get $$-f(x)\equiv x^2+2x \pmod{x^2+x+1}.$$

[sterile pumice]

Green4Applez

[primal moss]

So, $$f(x) \equiv -x^2-2x \pmod{x^2+x+1}$$

[sterile pumice]

Green4Applez

[iron surge]

Ah, yes; good point! I forgot that rule still holds for polynomials!

[wispy creek]

im confused about the name "primitive root"

the "root" part makes sense but what does the "primitive" part signify

[prime sparrow]

Well, its powers generate all the roots mod p, so it is “primitive” in a sense

[wispy creek]

oh yea that does make sense

[primal moss]

@spark shuttle does the explanation above make sense?

The solutions for f(x) follow from the final congruence

[urban peak]

how can i porve that for integer m, if m is even and m/2 is 1mod4, m can be written as a sum of two squares m=a^2+b^2 with coprime a,b

[prime sparrow]

I don’t think this is true, 18 is even and 9 is one mod 4, but the only way it is expressible as a sum of squares is 9+9

[urban peak]

sorry copied the question wrong. if m is even and m/2 is odd and if every prime diviiding m/2 is 1mod4, prove that m can be written as a sum of two squares m=a^2+b^2 coprime a,b

[spark shuttle]

yah this makes sense. thank u sm!

[primal moss]

Awesome!

[wispy creek]

i can show u that m can be written as a sum of 2 squares but i cant prove the coprime part

for smth like m=2*5 *5 =50, it can be written as 25 + 25 and also 49 + 1

the first doesnt have coprime a, b

[sleek cove]

what are u talking ab soap

[wispy creek]

representing a number as a sum of 2 squares

[sleek cove]

but all u do is give an example

[wispy creek]

as i said, i couldnt prove the coprime part. but the existence of square representation part i can prove like a champ 😎

[urban peak]

The square part is fine it’s just the gcd part in which I am having trouble

[wispy creek]

ic. i couldnt make the gcd part work out either

[sleek cove]

i cant tell if ur meming or not

[wispy creek]

isnt this supposed to be logarithmic time ?

[proven cypress]

it depends on your convention. Here they mean linear in the size of the input, where size is measured in bits rather than by absolute value/magnitude of the quantity

[wispy creek]

ah makes sense. thanks

[sacred junco]

I have a question about this problem, when it says that 3 | m^2 + n^2, is it possible to split it into 3 | m^2 and 3 | n^2? If not I'm unsure how to approach this

[sleek cove]

yeah, this is true from dn theorem

@sacred junco

[sacred junco]

is it the additive property?

[sacred junco]

The additive property is not true in general, for example 6 | 2+4, but 6 doesnt divide 2 or 4.

To prove the exercise, first note that 3 | m² + n², this means that there exists an integer k s.t.
i) 3k = m² + n²
Now do division with remainder of m and n by 3, which gives you
ii) n = 3a + r
iii) m = 3b + s
If you can show that r = s = 0 you are done. You can show that by squaring ii) and iii), then adding them together so you have an expression for m² + n², now compare coefficients with i) and conclude that r=s=0. Here its important that the remainders r and s can only be numbers from {-2,-1,0,1,2}

[torn escarp]

your set of remainders can be made much smaller, just {0,1,2}. If you square every one of these possibilities mod 3, you get the set {0,1} since 2 is not a square mod 3. Now the problem becomes looking at m^2+n^2 mod 3 as being, can we make 0 mod 3 by a combination of two numbers in this set where they're not both 0? The answer is no, since 0+1, 1+0, and 1+1 are all nonzero mod 3, so it must mean 0+0 is the only possibility.

[sacred junco]

I do have a follow up question , while the additive property is not true in general, isn't it true in this case? Since we are trying to prove that 3 | m and 3 | n

[torn escarp]

probably not a good idea to think of it as some kind of property since it doesn't really hold in any generality

at best I'd say if p divides a+b then we know either p divides neither of them or both of them, but never only one of them

you could try to prove that, since that's pretty close to what you want, I'll help if you want

[sacred junco]

Isn't that euclids lemma? I wrote up a proof but I'm unsure if its really logical tbh, I can DM you a picture of it if youre up for it

[torn escarp]

not quite, since euclid's lemma is the product not sum

plus this is sort of saying the opposite, p doesn't ever divide just one, it either divides both or neither

not quite, not really meaningful to compare them like that though

[sacred junco]

Ah I see

Could we use the fact that since 3 divides m and n, that m/n can take the value of either 3k, 3k+1, or 3k+2? i.e 3 different cases?

[torn escarp]

I don't follow, are you talking about your old problem or this new one

[sacred junco]

exercise 4.3

[torn escarp]

you can't assume 3 divides m and n, that's what you're trying to prove

if 3 does divide m and n, it doesn't mean m/n can take those values either

m=3, n=9 you have m/n=1/3 which doesn't work for example

[sacred junco]

Ah i see

I also have a question about this. Why is it valuable to mention that ab-bc = 1? Is there something that I can infer from that statement

[leaden swan]

Yes,that allows you to prove this using bezout

[sacred junco]

To be honest, never heard of bezouts identity

[sleek cove]

have you heard of eden identity?

[wispy creek]

do u still need help with that ?

[atomic gale]

I'm a bit confused here. What exactly is a complete set of residues?

Like I have this and my book says it's a complete set but what makes it that?

<@&286206848099549185>

[primal moss]

In this context, a complete set of residues means that you have all the possible residues mod 11

so every integer between 0 and 10 inclusive

@atomic gale Wait just to be clear, you know what a residue is correct?

[atomic gale]

Yes and I understand now.

Thank you.

[primal moss]

Awesome!

[red drift]

can someone teach me how to get started on this problem?

[gilded jacinth]

its a lot of bezouts identity shenanigans

[wispy creek]

for the first one lets say, u can start by assuming gcd(a, 1) = d. so d divides a and 1. but the largest number that can divide 1 is 1, and 1 also divides a. so d = gcd(a, 1) = 1

[dusty dragon]

Hi guys! If I fix an odd prime $p$, is there a way to generate another integer $n$ such that $\varphi(n) = \varphi(p) = p - 1$ where $\varphi$ is the Euler totient function

[sterile pumice]

opengangs

[dusty dragon]

If you want the question directly

Oh wait, I think n = 2p would work

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

[red drift]

thank you!!!

[red drift]

is that literally the answer to part a?

[wispy creek]

yea

[red drift]

do we need to any more then that? i feel like we do

[wispy creek]

sure, u can go ahead and make it more rigorous, but thats pretty much all there is to it.

[red drift]

okay, so for part b, i see how you did part a but for part b, i cant make an integer divisble by 0

so how would that work

[wispy creek]

u dont want an integer to be divisible by 0, u want 0 to be divisible by an integer

what integer(s) divide 0 ?

[red drift]

none lol, but thats how i interpreted it

[wispy creek]

why not ?

[red drift]

oh, wait

all integers then

[wispy creek]

yeah

so u only need to care about a

[red drift]

ok, so.... could i say assume gcd(a,0) = f, f an element of all integers, f divides 0 and a and the largest number that can divide a is a and 0 divides a so f = gcd(a,0) = a?

@wispy creek

[wispy creek]

what if a = -5 ?

is -5 the largest integer that divides -5 ?

[red drift]

no because there are greater values that can divide -5?

[wispy creek]

yeah and what is the biggest one ?

[red drift]

5a? because a could be any integer and multiplied by 5, it can be divide -5?

[wispy creek]

a divides b and b divides a are very different things. ur mixing up these two

[red drift]

this is so confusing 😭

[wispy creek]

im asking u, what is the biggest number, such that -5 is divisible by that number

[red drift]

oh well, there is no biggest number right?

[wispy creek]

ok try this then, write -5 = AB, maximize A and minimize B

[wispy creek]

why not ?

maybe this will help, -5 = 5 * (-1)

[red drift]

so u just took the absolute value of -5?

[wispy creek]

just factored it, but sure u can think about it like that too

anyways all this was to point out that if a is negative then a has a larger factor than a, namely -a

if a is non-negative then a is the largest factor of a

both cases can be summed up nicely using absolute values

[red drift]

oh, so all u did was just factor 5?

i thought u were talking about all numbers that can be divided by 5

lol

[red drift]

@wispy creek , how does this answer sound, Assume gcd(a,0) = f, f is an element of all integers. So f divides 0 and a and the largest that can divide a is a. If a is negative, then +a will be the greatest divisor of -a. So f = gcd(a,0) = a?

[wispy creek]

the largest that can divide a is a

thats not true

If a is negative, then +a will be the greatest divisor of -a

+a is literally the same thing as a

and then why are u considering -a when a is already negative ?

[red drift]

hm okay, but what is true then for the first statement you said?

[wispy creek]

we discussed this earlier that if a is negative then a is not the largest factor of a

-5 is a factor of -5 but we can do better, like how 1 is a factor of -5

and the largest we can do is when we say 5 is a factor of -5

[red drift]

ohh so |a| is the greatest divisor of a?

[wispy creek]

yes

[red drift]

oh wow

is there even a need to bring in another variable?

[wispy creek]

its easier to refer to the gcd that way but u can do without too ig

[red drift]

oh okay

[red drift]

@wispy creek for c, i said Assume gcd(a, a+1) = g, g an element for all integers. G divides a and a+1 and the largest number that can divide a+1 is simply 1. For example, a = 7 then the gcd(7,8) would be 1 because 7 and 8 dont share common divisors. This works in the negative direction as a = -7, then the gcd(-7,-6) is 1 because -7 and -6 dont share common divisors. So g = gcd(a,a+1) = 1

[wispy creek]

largest number that can divide a+1 is simply 1.

why is that ?

if i let a = 3 then a + 1 = 4 is divisible by 2 for example

[red drift]

but 2 is not divisible by 3

[wispy creek]

u mean to say 2 doesnt divide a = 3?

in any case, why should i care if 2 doesnt divide 3 ? ur telling me in ur proof that a + 1 is only divisible by 1 but i just found an example where a + 1 is divisible by 2

[red drift]

i thought the point of the gcd(x,y) is that both numbers have to have common divisors and whatever number is the greatest divisor makes it true

[wispy creek]

yes but ur proof is not saying that

[red drift]

i need to explicitly state that?

[wispy creek]

no thats not what im saying, i mean ur proof is asserting something false

[red drift]

oh

[wispy creek]

in ur proof, ur saying "a + 1 is only divisible by 1 where a is an integer"

that is clearly false, as i already gave u an example

for this problem u have get a bit clever

heres a hint: if d divides a and b then d also divides a - b (in fact d would divide am + bn for any integer m, n)

and im going sleep sleep 😪

[red drift]

oh okay, thanks for the hint

[leaden swan]

You could find all the possible square roots using CRT and it doesn't like there is a better alternative for this

Suppose n is of form ${p_1}^{k_1} {p_2}^{k_2}...{p_l}^{k_l}$ where each prime is odd,there are $l^2$ solutions

[sterile pumice]

Buncho Dragons

[leaden swan]

I guess you can predict the behaviour of 2 too, but that would be a bit more work

You reduce this to solving a system of CRT equations

And x^2-1=0(mod p^k) always has 2 solutions when p is odd

And 2 solutions if p is 2 and k is not 3

And 3 solutions if p is 2 and k is 3

Is any one of them 2?

Ok,there should exactly be 8 solutions

You can enumerate them

Mathematica can solve CRT problems right?

Let p_1,p_2 and p_3 be your primes

Is the number just p_1 p_2 p_3?

Or are there powers

Ok,solve 8 equations

1. x=1 mod p_1 ,x=1 mod p_2, x=1 mod p_3
   2)x=-1 mod p_1,x=1 mod p_2 and x=1 mod p_3
   3)x=1 mod p_1 ,x=-1 mod p_2 and x=1 mod p_3

The other 5 equations are similar to this with position of -1 and 1 changing

[leaden swan]

2^l mb

[leaden swan]

If you did what I said,should be correct

Looks good

[compact walrus]

how can i achieve this by the principle of complementation?

my process is:

1. count all possible numbers between 3000 and 6000 which is 3 * 9 * 8 * 7 = 1512
2. then count all the possible numbers lower than 3456 which should be, 1 * 4 * 4 * 4 = 64, am I missing anything here?

then 1512 - 44 = 1448 which is not the desired result. 😦

[haughty lichen]

Yes if your 2nd number is less than 4 then 3rd and 4th can be any number

For example 3289 is valid

So split it up if 2nd number is {0,1,2,3} or if 2nd number is 4 - and do the same for the following digits

[compact walrus]

okay let me try..

so lower from 3456 should be:

1. 3 {0,1,2,3} {0-9} {0-9} = 1 * 3 * 8 * 7 = 168
2. 3 4 {0, 1, 2, 3, 4} {0-9} = 1 * 1 * 3 * 7 = 21
3. 3 4 5 {0, 1, 2, 3, 4, 5} = 1 * 1 * 1 * 3 = 3

so 1512 -( 168 + 21 + 3) = 1320

I am off by one 1 from the answer...

is my calculation correct?

[haughty lichen]

Well you want lower or equal to 3456

[compact walrus]

oh okay...right...i want equal to be deducted to get get higher than 3456. Thank you very much.

[shut echo]

can someone help me with this?

I started with the fact that a^2-a must belong to S

Since a(a-1) belongs to S and gcd(a,a-1)=1=gcd(a-2,a-3) a-1 should also belong to S

using the same logic I can go on- a-2, a-3... Belongs to S

Is this approach correct? And how to get to the bigger elements (positive infinity)

[torn escarp]

oh interesting

I think I found it

no nevermind lol

I missed a sign when simplifying a^2 - (a^2-a) and thought I got -a

I suppose we just need to get arbitrarily large elements, we can take x^2-y and pick x to have the largest absolute value in our set so far and y to be the most negative element, I think we can always push this larger

[shut echo]

Ahh yeah i think that works

[torn escarp]

it's possible I misunderstand your conditions on a since I didn't really read what you wrote I just took your result and ran with it

[shut echo]

Ig you should read once cause I'm not sure if I can use the first condition the way I did

[torn escarp]

hmm I don't think that works

even though we know we have a and a^2-a we can't say a-1 is in the set because of that

[shut echo]

yeah i kind of used the converse

[torn escarp]

I wonder if we can do something like take f(x,y)=x^2-y and then do some sort of induction on what we can get to with iterating it in different ways, but somehow requiring part a) as the base case

ok, what numbers actually satisfy gcd(a,b)=gcd(a-2,b-2)=1?

I feel like this is a kind of harsh restriction

[shut echo]

Consecutive odd numbers and consecutive numbers

There could be others too actually

Like (7,11 or 13)

[torn escarp]

hmm

[shut echo]

Can we manipulate a^2-b and b^2 -a to get something nice

[torn escarp]

I was playing with that earlier but just kinda felt like it was endless but maybe we should play with that

like once we have a^2-b we can look at b^2 - (a^2-b) = (b+a)(b-a)+b maybe

[shut echo]

yeah

[torn escarp]

also was sort of hoping that f(x)=x^2-x could be iterated f(f(x)), f(f(f(x))), etc and get some nice closed form out of that but

nothing stood out to me

[shut echo]

But how can we construct the set of integers since we gotta keep track of what numbers we're getting and whether we're missing out any number

[torn escarp]

hmm

[shut echo]

Like can we show that 1 or 0 belongs to S

[torn escarp]

maybe a piece of it is showing that we can take f(x,y)=x^2-y and pick numbers so that this converges to 1 or 0 or something

[shut echo]

yeah

[torn escarp]

like a decreasing sequence and then from there we can use f to build up anything I think, well ok let's see here

if we have 0, then we can construct -x from x by doing 0^2-x

if you have 1 or -1 as well then we can put in 1^2 - (-x) = x+1

[shut echo]

yup

[torn escarp]

so maybe we do just need to show from condition a) we can descend with x^2-y to 0 and 1 or something

just trying to establish what we really need to get there

[shut echo]

yeah

[torn escarp]

kind of feels like a funky version of the euclidean algorithm now

[shut echo]

Can you explain how you're using euclidean algorithm

[torn escarp]

well I'm not using it, just saying by analogy it's sort of similar feeling

like when you start with say, (35, 11) = (35 - 3*11, 11) = (2, 11) = ...

[shut echo]

oh i get what you mean

[torn escarp]

kind of imagining this process but with x^2-y

so ok, here's one way to back track, to get 0 we need 0=x^2-y so y=x^2

clearly x and y are not relatively prime unless x=1

but this is nice, getting 1 gets us 0

[shut echo]

yeah

So we just need to get 1

[torn escarp]

so let's see, 1=x^2-y so I guess rearrange this to make y=(x+1)(x-1)

idk if this is better or worse, but maybe we can show we can get something that can go into this from the gcd condition... 😬

alternatively y+1-n^2 = (x+n)(x-n)

y=(x+n)(x-n) + (n+1)(n-1)

just praying that writing something down will resemble something on the other end with a,b hmm

[shut echo]

btw i have another idea: since a is in S can we express a as d^2-b or d^2-d or b^2-d and say that d belongs to S?

ig in this method too we cannot keep track of what numbers we get systematically

showing 1 is in S seems really hard tho

[torn escarp]

yeah, I'm playing with inequalities trying to see if there's a way to pick x,y so that |x^2-y|< min(|x|,|y|)

[shut echo]

okay

[torn escarp]

or something like that, since that can't exactly hold as strict inequality always ofc

something maybe,

$\gcd(a^2-b, b^2-a) = \gcd(a^2-b-b^2+a, b^2-a) = \gcd((a+b-1)(a-b), b^2-a)$

[sterile pumice]

Merosity

[torn escarp]

just trying to get the gcd condition to relate to the x^2-y condition in any way at all, since we need them to interact somehow

[shut echo]

Okay

Can we not assume that a and b are odd such that it satisfies (a) and then see how to get 0 or 1

hmm it doesn't really work

gcd(a,b)=1 means there exists k such that we get to gcd(a-kb,1)

[torn escarp]

hmm

another kind of weird thing maybe

we know there's x,y and u,v such that ax+by=1 and (a-2)u+(b-2)v=1

[shut echo]

Yes

[torn escarp]

I think that gives me an idea

we can suppose a>b and write a=b+c

then we have gcd(a,b)=gcd(b+c,b) = gcd(c,b)=1

and gcd(a-2, b-2)=gcd(b+c-2, b-2) = gcd(c, b-2)=1

this is nice because it means c is just any number that's relatively prime with b and b-2 is a possibility

gives me a better view of it, I'm gonna head out for a bit maybe think about it tomorrow

[shut echo]

sure I'm falling asleep :/

[torn escarp]

maybe you'll find a solution in your dream and we won't have to think about it tomorrow

maybe you'll find a solution in your dream and we won't have to think about it tomorrow

[shut echo]

haha yeah

[torn escarp]

lol later

[sleek cove]

maybe you'll find a solution in your dream and we won't have to think about it tomorrow

[sacred junco]

Wait this problem isn’t true right or am I missing something?

Problem 3

Like just try q=3 and p=5

You get (1-1/p^s)(1+1/p^s) = 1/(1-p^2s)???

[light flicker]

@sacred junco yeah that seems wrong. I think it should be correct if the right hand side is 1 - 1/p^(fs) raised to the gth power

[shut echo]

didn't have any dreams😓

[sacred junco]

I have a question, if 31 | ab, and 31c^2 = d^2, then how would I prove that 31 | d?

[leaden swan]

31 | d^2 clearly

Now use that d^2 and d have the same primes in their factorisation

[sacred junco]

I'm not sure what u mean that 31 | d^2 clearly

is it because d^2 is equal to 31c^2

Actually i see what you mean

If thats the case, how could I prove that 31 | c?

is it the same method

[leaden swan]

You know d has 31 in its prime factorization

So d^2=(31)^2 k for some k

(31)^2 k=31 c^2 implies (31)k=c^2

Now do the same thing as before

[sacred junco]

ah i see thanks

never mind figured it out

[wooden crater]

another perhaps simpler way:
if p is prime and p | ab, then p | a or p | b.

since 31 is prime and 31 | d^2, then 31 | d or 31 | d. so 31 | d, clearly.

[compact walrus]

I do not understand why the subtraction? {3-1,5-1,7-1} ?

[leaden swan]

The set {n_2+1,n_3+1,n_4+1} is {3,5,7}

[compact walrus]

the divisor count of n is (n_1+1)(n_2+1)...(n_k+1) and as it has 105 divisors, then it can be written as
(n_1+1)(n_2+1)...(n_k+1) = 105
or, (n_1+1)(n_2+1)...(n_k+1) = 3.5.7

after that how the k=4 or the missing p_1, hence n_1 =0 affects the reasoning?

k=4 , n_1=0 is only applicable for the number 105 so the factors of 105 can be written into, (n_2+1)(n_3+1)...

there is a reasoning, the 105 number has only p_2 = 3, p_3 = 5, p_4 = 7 primes ...they are scaling the degrees up to find a factor @leaden swan

hence the n_1 = 0

[leaden swan]

They are also applying n_2>1 ,n_3>1 and n_4>1 condition I think

[compact walrus]

yes true.

[leaden swan]

You have to pick 3 (n_k) s such that n_k+1=3,5 and 7

[compact walrus]

oh i think i kinda get it now...

but this technique could be a little verbose...

thanks @leaden swan

[atomic gale]

Hey so I'm confused here as to how they jump through the 2 listed steps.

Like I get everything else but those 2 I marked in red I don't get.

[atomic gale]

<@&286206848099549185>

[sacred junco]

They just used exponent rules

[atomic gale]

How so?

[sacred junco]

exponent rules

x^{a+b}=x^a*x^b

and so on

[atomic gale]

I know that 11^(12n+6) = 11^12n*11^6

[sacred junco]

yes

[atomic gale]

So wouldn't this only work though if both sides were 1?

[sacred junco]

you know 11^12 = 1 by FLT

[atomic gale]

Ooooooooh

See that's where I was confused.

[regal aspen]

@sacred junco Hey hobo

[sacred junco]

yo

[red drift]

@wispy creek so what i have for this is,
Let a be arbitrary and b,c,d, an element of integers such that
a+b = c gcd(a^2 - b^2 + 1, a + b)
a^2 - b^2 + 1 = d gcd(a^2 - b^2 + 1, a + b)
am i on the right direction?

[leaden swan]

@red drift just use bezout

Yea,your approach works too