elementary-number-theory

[serene pasture]

How do I do this?

Without brute forcing obvi

[swift lodge]

hint:||primes||

[shell thistle]

1

[serene pasture]

?????

1 is not divisible by 2…?

[shell thistle]

That’s my guess.

[modest vector]

@serene pasture prime factorize the numbers:
9=3x3
8=2x2x2
7=7
6=3x2
5=5
4=2x2
3=3
2=2

then take the largest prime powers:
2³x3²x5x7

[covert valve]

hello new here wondering were i go to ask for help about volume and geometry

[wanton torrent]

#❓how-to-get-help

Hey guys!

So for p prime, I don't know how to show that $(\pm i)^2 \not\equiv (\pm j)^2 \mod p$ for $1 \leq i < j \leq (p-1)/2$

[sterile pumice]

mns

[heady basalt]

Well first of all, you really just need to show i² ≠ j² [p]

(since adding a minus sign does nothing, it's a square)

Second of all, recall you are allowed to add and subtract things in integers mod p

[wanton torrent]

Right

I am reading

ok So

we know that $p \nmid i^2$ and $p \nmid j^2$ as if it were the case then p wouldn't be prime

[sterile pumice]

mns

[wanton torrent]

Then we're left to show that $p \nmid (i^2 - j^2)$

[sterile pumice]

mns

[torn escarp]

I think it's easier to go directly, if p | j^2-i^2 then this implies p | j-i which means they're equal

I'm leaving out crucial details for you to think through

[wanton torrent]

oh yeah the passage from then to p| j - i was a big step

[torn escarp]

I said for mns to to think through not griff to think through smh

[mossy sun]

oh my apologies

[wanton torrent]

oh

lol

😦

[mossy sun]

may not have read what you said right merosity lol

[wanton torrent]

I won't lie I did and it was just getting to (i-j)(i+j) = i^2 - j^2, the rest I could do

this proof is by contradiction then

not directly?

[mossy sun]

yeah I'd say it's contradiction, or rather you can think it's a proof of the converse

[wanton torrent]

+1

Thanks!

[mossy sun]

you're proving that if 1 <= i, j <= (p-1)/2 and i^2 = j^2 then i = j

you may want to see why this fails to be true if i and j can be a bit bigger

[wanton torrent]

I wasn't expecting that

[mossy sun]

pick a few (odd) primes p, and change the bounds to 1 <= i, j <= (p+1)/2 instead

it won't work anymore

why?

[wanton torrent]

for i = (p-1)/2 and j = (p+1)/2 we would have i^2 == j^2

[mossy sun]

yeah, because then i+j = 0 mod p

[wanton torrent]

I see

thanks again!!

[mossy sun]

np!

[sacred junco]

how do you minimize 4(x-y)^2+(y+3)^2+(x-6)^2+1977

[cosmic raptor]

can someone help me with multipication

[stiff rivet]

are you sure you dont want to be in #prealg-and-algebra or a help channel?

[sacred junco]

need help

[fervent crest]

You can try to prove the contrapositive

Or proof by contradiction if that makes more sense

So assume that a is even, then what happens

[sacred junco]

well we have $a \mid b$ with $a, b \in \mbb{N}$. $a + b$ is odd which means $a + b = 2k+1$ right

[sterile pumice]

ZZZ

[fervent crest]

Yes

Now start with what I said, that assume a is even

[sacred junco]

so $a \mid b \implies \exists r$ such that $b = ar$

[sterile pumice]

ZZZ

[sacred junco]

oh if $a$ is even then we have $a = 2n$ and $a + b = 2z + 1$

[sterile pumice]

ZZZ

[sacred junco]

so $2n - 2z = 1 - b$ which implies that $1 - b$ is even which must mean that $b$ is odd?

[sterile pumice]

ZZZ

[fervent crest]

Yes that is correct

[sacred junco]

then shouldn't i instead assume that b is even

and show that a is odd

well, I could start by saying

[fervent crest]

Well no no

We're on the right path

We're very close

[sacred junco]

that if a + b is odd then a and b cannot both be odd

[fervent crest]

So we started by assuming a is even and we want to find a contradiction. We used a+b is odd to show b is odd. We still haven't used the fact that a | b

So now we have 3 facts available to us: a is even, b is odd, and a | b

[sacred junco]

a | b means b = ak

a is even so a = 2n, b is odd which means b = 2z + 1

oh

2z + 1 = 2an which is impossible

because 2an implies that an = z + 1/2

no?

[fervent crest]

Exactly

That is correct

So that means a can't be even

[sacred junco]

i see

this must mean the opposite is true

thank you

[fervent crest]

Np

And now you should write it down

[sacred junco]

we can actually shorten it

wouldn't it suffice to say

assume for a contradiction that $a$ is even, i.e. that $a = 2n$. by the definition of divisibility, $a \mid b$ implies $b = ar$ for some $r \in \mbb{Z}$. Then, if $a$ is even $b$ must be odd as their sum is odd. Then we have $2k + 1 = b$ and $2k+1 = 2ar$, which is a contradiction as 2k+1 is odd for all integers k and $2(ar)$ is always even

[sterile pumice]

ZZZ

[sacred junco]

well that's not really a shortened version, but yes

[fervent crest]

Well you probably should justify a bit more why a is even then b is odd

Also a more concise way of seeing it is that if a is even then 2 | a | b so b is even as well which means a + b is even

But I think it's good to discover your own ways

[sacred junco]

is it not axiomatic that if a + b = 2k+1 then a = 2n and b = 2r + 1 or vice versa?

[fervent crest]

No?

What axioms will say that

[sacred junco]

well a + b is odd iff a is odd and b is even or vice versa, no?

how would i really justify that further

[fervent crest]

Well this is a perfect justification

[sacred junco]

oh, yeah i suppose that works

[fervent crest]

Or you just notice that if b were to be odd then a+b will be even again so b must be even

In any case yeah it's not a major issue

[sacred junco]

alright tyvm

[wanton torrent]

So

Hello guys

Trying to understand why the (3p/2, 2p) interval

[sacred junco]

help pls

[stiff rivet]

what did you try?

[sacred junco]

i tried to consider two cases

a = 2k

and 2 = 2k+1

the case is pretty self evident for a = 2k

we have $4k^2 + 2$ which is obviously not divisible by 4

[sterile pumice]

ZZZ

[stiff rivet]

ok, whats giving you trouble in the other case?

[sacred junco]

well we have $(2k+1)^2 + 2 \implies 4k^2 + 4k + 3$ which is not divisible by 4 either

[sterile pumice]

ZZZ

[sacred junco]

so, would it just suffice to say that $4(k^2 + 0.5)$ is never an integer because no square of an integer can produce a fractional value?

[sterile pumice]

ZZZ

[sacred junco]

and similarly for the second case

[stiff rivet]

i wouldnt write it like that

[sacred junco]

how would you, if you dont mind?

[stiff rivet]

i mean, numbers of the form 4k + r with 0 < r < 4 arent divisible by 4

[sacred junco]

ah right

[stiff rivet]

your justification works i guess, i just dont like how it looks

you can justify this without "moving to Q"

[sacred junco]

ah okay, thank you!

[stiff rivet]

but your proof is correct

[sacred junco]

will keep that in mind sir

[sacred junco]

can anyone help?

I'm setting up the equations to be:

$\frac{a - 4}{13} = q_1$ for some $q_1 \in \mbb{Z}$ and $\frac{b - 9}{13} = q_2$ for some $q_2 \in \mbb{Z}$

[sterile pumice]

ZZZ

[sacred junco]

then we have $a = 13q_1 + 4$ and $b = 13q_2 + 9$

[sterile pumice]

ZZZ

[sacred junco]

actually for $a)$ we can leverage that $ab\bmod{m} = ((a\bmod{m} )(b\bmod{m})\mod{m}$, right?

[sterile pumice]

ZZZ

[sacred junco]

would appreciate some help

[stiff rivet]

this really depends on what you know

[stiff rivet]

if you have this, all of this should be easy

[sacred junco]

well in this situation we have b = 9 and a = a, let's say

with m = 13

but im not sure how to proceed

[stiff rivet]

so just compute 9*a = 9*4 and then reduce mod 13

[sacred junco]

why do we have 9 * 4?

[stiff rivet]

it says it in the question, right?

$a \equiv 4 \pmod{13}$

[sterile pumice]

Lochverstärker

[sacred junco]

oh

a = 13 + 4q

wait

[stiff rivet]

ok, so

if you dont know that you can work with representatives, you have to more work

[sacred junco]

I am being stupid lol, we just plug it in

[stiff rivet]

but if you have this, you can work with 4 instead of 13k+4

[sacred junco]

we can multiply $9(a \equiv 4(\bmod{13}))$

[sterile pumice]

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

[sacred junco]

right?

[stiff rivet]

i cant parse this

you can just multiply 9 by 4 and then reduce

if you have the required theorems

in general one can show that if $a_1 \equiv a_2 \pmod{n}$ and $b_1 \equiv b_2 \pmod{n}$, then $$a_1 + b_1 \equiv a_2 + b_2 \pmod{n}$$ and $$a_1 \cdot b_1 \equiv a_2 \cdot b_2 \pmod{n}$$

[sterile pumice]

Lochverstärker

[stiff rivet]

so at the end of the day this is just plugging in and then reducing mod 13

[sacred junco]

okay

so

\begin{align}
b_1 &\equiv 9a\pmod{13} \
a_1 &\equiv 4\pmod{13} \
9a\pmod{13} \cdot 4\pmod{13} &\equiv 36a \pmod{13}.
\end{align}

[sterile pumice]

ZZZ

[stiff rivet]

you dont have to tex it, you can just use = if you want

[sacred junco]

oh ok

[stiff rivet]

but like using this for the first one you get

$$9a \equiv 9\cdot 4 \equiv 36 \pmod{13}$$

[sterile pumice]

Lochverstärker

[stiff rivet]

where in the first $\equiv$ i used the fact that $a \equiv 4 \pmod{13}$

[sterile pumice]

Lochverstärker

[stiff rivet]

and then its just a matter of reducing 36 mod 13

so you subtract 13 until you are below 13

and get

uhh

10

[sacred junco]

10?

like this?

[stiff rivet]

all the other ones are solved the same way, you just replace a by 4 and b by 9

[sacred junco]

but isn

[stiff rivet]

sure

[sacred junco]

isn't a = 4mod13

not a = 4

[stiff rivet]

yes

but all the questions just ask for equivalence

and if you are only using \equiv and not = you can replace every occurrence of a by 4

you could also use 17 or -9 or infinitely many other things

now tbf all of this is assuming you have the theorem i quoted above

[sacred junco]

yeah i do

[stiff rivet]

you can also work with 13k+4 and then do algebraic manipulations until you are done

ok

so yeah with this you can just work with an representatives

[sacred junco]

but how would that work

you can't set up a system of equations

[stiff rivet]

in the first one you have (13k+4)9 = 13*9*k+36 = 13*9*k+13*2+10 = 13(9k+2) + 10 \equiv 10 mod 13

so you have to carry a lot of "baggage" with you for no reason

with the theorem you have you can just take any representative of a

in this case the smallest, namely 4

and work with that

and then reduce after every arithmetical operation to the smallest representative and continue

[sacred junco]

i see

thank you

[stiff rivet]

one thing worth noting

so if you have a^3

you could do (a^3) mod m

but you can also do (((a^2) mod m)* a mod m) mod m

the latter is computationally easier, because the numbers dont get quite as big

it doesnt matter for small numbers if you have a calculator but if you do it on paper or for larger numbers it does

[sacred junco]

how do I do c)?

[sacred junco]

oh okay, sorry i didn't see this (also let me know if i should ping on reply or not)

[torn escarp]

what's your best guess?

[sacred junco]

leveraging

but idk how

[torn escarp]

take a guess

[sacred junco]

i mean, we need to find c

so do i compute the sum of a + b + c?

[torn escarp]

pretend all the (mod 13) are gone

then the problem becomes a=4, b=9 and then compute c=a+b

[sacred junco]

why do i pretend its gone?

[torn escarp]

because I told you

[sacred junco]

XD

fair enough

umm

[torn escarp]

so with the modified problem what's your guess

times up, good luck

[sacred junco]

sorry , my mother called me

so essentially what I gather

is that $a \equiv 4\pmod{13}$ and $b \equiv 9\pmod{13}$, then $a + b = 13\pmod{13}$, then substituting this in we have $c = 13\pmod{13} \pmod{13}$

[sterile pumice]

ZZZ

[sacred junco]

since $13\pmod{13} = 0$ does that automatically imply that $c = 0$? is this the correct method?

[sterile pumice]

ZZZ

[leaden swan]

Yes

[rotund maple]

I have a question from my classmate

prove that for every $n$, $p$ being an odd prime factor of $n^4-n^3+2n^2+n+1$ always satisfies $p\equiv1,4\pmod{15}$

[sterile pumice]

CollinGao-ALT

[unkempt void]

mod 13, yes

[wanton torrent]

Ok so I am having trouble with one problem

Let p,q be two carmichael numbers and n = pq

let f = (p-1)(q-1)

and suppose that e,d are integers such that ed == 1 mod f

Show that if (M,n) = 1 then M^(ed) == 1 mod n

I tried several approaches, namely with M^(p-1) == 1 mod p and M^(q-1) == 1 mod q and using the chinese reminder but couldn't

Then I also used Euler's Lemma with M^(phi(n)) == 1 mod n but couldn't go further with phi(n) = phi(pq)

[sacred junco]

Is this even true? Tried it with n=561*1105, M=19, and ed = f+1. M^(ed) is like 109414 mod n

I found something online saying you can do RSA with one Carmichael number and one prime, so maybe that's what the question originally was? Maybe not though because there's still an unmentioned gcd restriction between the two numbers in that case

apparently that also makes the encryption "fatally vulnerable" but that's another story

[sacred junco]

wait you can recover it with ed == 1 mod f implies ed + kf = 1, then (e,f) = 1 and (d,f) = 1 meets those restritictions on e and d for doing RSA with n being a prime times a Carmichael number

So it's likely this was the original question

@wanton torrent

[wanton torrent]

uh

this was an exercise on a test

[sacred junco]

is there something you left out? it seems not to be true unless I calculated something wrong

[wanton torrent]

Nope

Now that I see, I believe the professor meant M^ed == M mod n

because this is possible

and indeed I found a counter example for the statement

p = 561 and q = 1105

n = pq = 619905

f = (p-1)(q-1) = 618240

e,d in Z with e = 11 and d = 168611. We can verify that indeed ed == 1 mod f

pick M = 7, then (M,n) = 1 but M^ed == 474052 =/= 1 mod n

[static sapphire]

That’s trivial, just factor as
(n^2-n/2+1/2)^2+(3/4)(n+1)^2, then -3 is a square mod p. By QR we know p=1 mod 3. Do a similar factorisation to get p=1 or 4 mod 5. Then Chinese remainder theorem for the final answer

[wanton torrent]

[rotund maple]

OH so damn calculations

I thought that there were something that looks delicate

[sacred junco]

I'm out of practice, why is -3 a square mod p from that?

[rotund maple]

that was simple

just simple calculations to show that (n+1)/2 mod p isnt 0

[wanton torrent]

Back

Need to verify something

Let n be a Carmichael Number, p a prime such that p divides n

Let n = pq for some q in Z

nvm

is there any way we can relate exponents of equations with congruences?

For instance, if we have a^b == c^d mod p can we do something with b and d mod something?

[torn escarp]

in theory there are phi(p-1) generators we can pick from, so you could take g to be one, and write a=g^r and c=g^s and then you can look at g^(rb)=g^(sd) mod p and consider rb=sd mod p-1

in practice this might not be the best thing to do, but I don't know what you're wanting to do with the exponents

[wanton torrent]

oh

yeah that is interesting

[wanton torrent]

5x^2 + 7x + 12 == 0 mod 15

how would you start?

i cant take the 5 out from x^2

[torn escarp]

reduce mod 3 and mod 5 separately and solve there, then recombine the solutions to get the mod 15 solution

[wanton torrent]

how?

[torn escarp]

chinese remainder theorem

solve it mod 3 and mod 5 first, then play around with it a bit to see if you can work out how to combine them, then if you're still stuck show me what you got for your solutions mod 3 and 5 and what you did to try to combine them and we can go from there

[wanton torrent]

i cant reduce to mod 3 and mod 5

[torn escarp]

like this
5x^2 + 7x + 12 == 0 mod 3
5x^2 + 7x + 12 == 0 mod 5

well if you really can't reduce you can just do it the hard way

and just plug in all numbers from 0 to 14 and see what works or not

[wanton torrent]

oh ok thanks

[wanton torrent]

Managed to do it, thanks!

[torn escarp]

cool you're welcome 👍

[wanton torrent]

holy

why does python gives 4/57 = 0.07017543859649122

but this fraction is supposed to have infinite decimals

(ok, I see the infinite decimals) but why it stops here

[unkempt void]

Did you expect it to give an infinitely long string

But yeah ig it'll be to do with how many digits it stores for numbers

[wanton torrent]

that would be

interesting, if I haven't read this thing now I would thought 4/57 have finite decimals lol

[torn escarp]

it happens to be period of 18, and that's only 17 digits haha

[wanton torrent]

yeah I noticed that after the last 2 is a 8 and then the remainder is 1 again so it repeats all over again

[torn escarp]

just input 4/57 in wolfram alpha,

gotcha

if you're bored, try to see if you can figure out how to determine the period of the decimal expansion of a/b without computing it the brute force way

[wanton torrent]

I will think about that, thanks!

it might come later in the book tho

[torn escarp]

I think it's more fun to figure stuff out on my own than have someone else in a book tell me, personally haha

[wanton torrent]

obviously it is!!!

I will!

[torn escarp]

I sort of worded that sneakily, "try to see if you can" cause what I have in mind to relate it to is a well known number theory thing, but it's not exactly known for being easy to compute

[wanton torrent]

I see, do some examples to try to find a pattern?

are you acquainted with diophantine approximation?

[torn escarp]

somewhat, it's interesting but I'm not an expert at that or anything

[wanton torrent]

what are you an expert at?

I wonder if this is somewhat similar to analytic number theory?

And how much analysis would be needed for this?

[mossy sun]

project euler moments

you can compute arbitrarily many digits easily just storing the fractional part of (a/b)*10^n

[mossy sun]

but that doesn't help find cycle length

though it does tell us something important about it

[obsidian saddle]

So if you get 2x^2+x for mod 3 and 2x+2 for mod 5 is the answer mod 15 given by multiplying the two?

wait that isnt what you want to do

[south sedge]

does x0 mean when x=0 ?

[obsidian saddle]

Im missing context

x_0 is usually an index for the first element of a sequence

@south sedge

[south sedge]

i mean in coordinate geometry does x_0 mean the origin ?

as in x = 0

[obsidian saddle]

So this wasnt meant to be polynomial modular arithmetic but solving for x

[south sedge]

with any value of y

[obsidian saddle]

I see

[obsidian saddle]

It depends on the context

Sometimes people use (x_0,y_0) to define an arbitrary point in the plane

[torn escarp]

yeah solving for x

[south sedge]

mhmm

ok

thanks

[green shore]

Is this a property of divisibility?

That is, if $a$ is a divisor of $bc$ and $a$ is relatively prime to, for example, $b$, then it follows that $a$ divides $c$?

[sterile pumice]

tuturuuu

[torn escarp]

yeah, since a,b are relatively prime there are integers x,y such that ax+by=1 so now you can multiply by c to get acx+bcy=c, since you know a|acx and a|bcy, it divides their sum, which is just c

[obsidian saddle]

Damn I lost lol

[green shore]

I get it now, however what do you call that property, that if a,b are relatively prime, then we can find integers x,y such that ax+by=1?

Sorry I don't have any background in number theory

[west glade]

bezouts lemma/theorem/...

[obsidian saddle]

ok solved

[green shore]

Thank you!

[torn escarp]

yup you're welcome

[obsidian saddle]

No I didnt solve it lol

I just got x=-1 when modding by 5

idk a how to show for modding by 3

and x=0 for second one

oh

then i use it

[torn escarp]

it's a quadratic so it can have two solutions

[obsidian saddle]

okay lol im slow

i solved the quadratic formula but that is the slow way

cant i just test x between 0 and n

[torn escarp]

you can factor it

[obsidian saddle]

i tried but it looks ugly

[torn escarp]

2x^2+x=0 mod 3
x(2x+1)=0 mod 3

means x=0 or 2x+1=0 mod 3, you got the first one

[obsidian saddle]

oh wait

[torn escarp]

just keep solving 2x+1=0 mod 3 for x to get the second one

[obsidian saddle]

i see what i have to do now

[torn escarp]

cool

[obsidian saddle]

thanks so much

[torn escarp]

be warned, you can only split f(x)*g(x)=0 to mean f(x)=0 or g(x)=0 mod p for when p is a prime

if it's composite, like 15 was, that won't have worked out, yeah you're welcome

[obsidian saddle]

yeah

because prime ideal property

lol

i cant solve x^2+2x+2 = 0 mod 3

testing numbers is what ive been doing

alternatively i try to solve for 2^2 -4*1(2-3k)=a^2

so the discriminate is nice

i made a problem of solving 7x^2+8x+2 == 0 mod 18

oh

maybe there are no solutions lol

yeah

so i think thats it

it looks like it cycles from 1 to 2

idk how to prove no solution though

similarly i find that 2a+5=3k has no solutions

nvm i solved it

you can show that 2a+5=3k can be reduced mod 3 to be 2a+2=3k

nope lol nvm

a solution is a= 2

[obsidian saddle]

nvm

i learned how more

[obsidian saddle]

I think I proved something you were saying from before

but if you have an equation f(x)==0 mod p then you only need to check x=0,..,p-1?

because otherwise you can reduce multiples of p that you would be adding

so like if we take x^2+2x+2==0 mod 3

and we consider x=4 for example

I claim this is the same as x=1

We can say 1+3j represents the equivalence class for 1,4,…

If we substitute 1 + 3j into the equation

(9j^2+6j+1)+(6j+2)+2=3k

If we let k= (3j^2+2j+2j+2)

This reduces to 2=0

It can be done in generality though

[torn escarp]

yeah that sounds about right to me, I didn't meticulously read through the details but sounds like you're figuring it out 😎

[storm narwhal]

For primes p and q, are there only finitely many pairs (p^a, q^b), such that p^a and q^b differ by 1? Of course one of the primes has to be 2 (say p) and if the other is 3, then only possibilities are (2,3) and (2^3, 3^2). But what can we say when q is any odd prime?

[torn escarp]

actually it's been proven more generally and you can release the restriction on p, q being primes, this was called catalan's conjecture up until it was proven fairly recently and so now it's mihailescu's theorem

[storm narwhal]

Thank you very much for the information. It says that it has only one solution, even when we allow p, q, a and b to be any integers greater than 1.

[torn escarp]

yup you're welcome

[storm narwhal]

But I am still thinking : what about the cases when one of a and b is 1. I mean what about the solutions of 2^a = q+1, where q is an odd prime. Like (32, 31). Do we have some information in this case? Are they also finitely many?

[torn escarp]

well if b=1 then we have x^a=y+1, so for any x, a you plug in the answer will be y=x^a - 1

and on the other side if a=1 then x=1+y^b is the same situation, plug in y and b, and you get x

if you want to find multiple solutions say, y=x^a - 1 and y=z^c - 1 then you can equate them to get x^a=z^c and so you can get multiple solutions by juggling powers around

so for instance 63 = 64^1 - 1 = 8^2 - 1 = 4^3 - 1 = 2^6 - 1

the number of solutions for a given y will be the number of divisors of the power on y+1

so in that example y=63 so y+1=64=2^6 and 6 has 4 divisors, 1, 2, 3, 6

[gentle summit]

Hey im struggling to prove this one, can u help me to begin the proof using hensels lemma?

[torn escarp]

am I misreading it or should it be x^m=y since otherwise it seems to be in Z_{p^k} alone

I'm about to go to sleep, good luck

[wheat tinsel]

This was written some time ago, what's the accurate statement now?

[fervent grove]

200 digits is about 500 bits

we still can't really factor arbitrary 500-bit integers

[stiff rivet]

https://en.wikipedia.org/wiki/Integer_factorization_records

On December 12, 2009, a team including researchers from the CWI, the EPFL, INRIA and NTT in addition to the authors of the previous record factored RSA-768, a 232-digit semiprime.[3] They used the equivalent of almost 2000 years of computing on a single core 2.2 GHz AMD Opteron.

so yeah, it takes a while

[sturdy violet]

The book I'm reading affirms that if you can show that plugging in integers to a polynomial always yields an odd result then the polynomial has no integer roots.. how?

[torn escarp]

because 0 is even

[sturdy violet]

I mean, I guessed that but isn't 0 a gray area about being odd or even?

[torn escarp]

nope not gray area at all, it's even if you can write it as 2*n for n an integer

it's not odd at all because there's no integer solution to 2n+1=0

[sturdy violet]

Sure

Thanks

[torn escarp]

yup you're welcome

[sacred junco]

There's a claim that all natural numbers can be written as a sum of four or less perfect squares.
I've proven this, so I think it's true and fair to claim as a property of natural numbers.

I've even generalized it to terms raised to a 3rd power ( perfect cubes ), 4th power, and general kth power where k is positive integer.
But it's not clear to me what sort of utility this property has.

Like, it seems like we might want to say something about base representations.
Or we might go the other way and say that something about base representations entails these properties.

Are there any deeper motivations or uses of such summation properties in number theory?
Maybe they are used in other proofs?
Or perhaps it informs some intuitions about numbers that I'm unaware of?

[heady basalt]

If you proved it, better publish it because "can every integer be written as the sum of four cubes" is an open problem

[sacred junco]

Right. In my "generalization", I don't argue for 4 cubes.
Just a specific, fixed value regarding cubes.

[sacred junco]

Is there a name for this kind of problem?
Or maybe a family of problems?

[heady basalt]

It's called Waring's problem

But considering the first proof was provided by Hilbert in 1909, I'm somewhat skeptical of you having proved it as an easy generalization

[sacred junco]

That's nice, sarcastically speaking.

That's not particularly charitable.
But, I guess since that's how math culture currently is; a lack of charity it's fairly normalized.
Though, it's clearly pretty objectionable.

I didn't think for problems like this I'd run into the need for formal verification systems so soon.
I'll see about writing that up so I can check my work.
Thanks for the search term.

[heady basalt]

Charitable? What does that have to do with anything?

My point is that if a problem was proved in the 20th century using advanced tools by a mathematician of the caliber of Hilbert, it seems somewhat unlikely that someone could go ahead and prove it using what I assume are elementary tools without much trouble

It's not impossible, it's just unlikely based on my experience of the world

[sacred junco]

There doesn't seem to be much anything else fruitful or constructive coming from this.
I'm going to head off from here.
Have a nice day.

[sturdy violet]

Ivan, people come about beliving they proved something all the time, and even if ya did do something, there are 100 others who made some critical mistake

Nowadays you usually would have the proof published, or at least put in arxiv, at which point someone can find flaws or not in it and it can be reviewed

[sacred junco]

Duhon, if you're saying something like, people are so encumbered with false or invalid proofs that they feel collectively justified in using heuristics of skepticism, I hear that.
But there are ways to handle the skepticism or to express that skepticism in ways that are not outright dismissive or condescending.

See how the following reads differently:

"Hey, I've run into quite a few claims of having proven theorem T with elementary methods. I'm generally skeptical of these proofs because I have reason to believe they tend to be false. My reason is that people with more expertise than me seem to require sophisticated methods M to have proven T. So, perhaps you might find it prudent to check out some of those proofs to understand why they felt it was required to use M to prove T."

It's better but still far from perfect.
There's no invitation to any feedback for example.
In your case, it's a bit better.

I read it as something to the tune of "I have similar skepticism because of the aforementioned reasons. But, if you post your proof on something like Arxiv, then maybe I or others will be able to engage and assess your proof more charitably."

[sturdy violet]

What I'm saying is that usually people will shut you down if you just say "I proved it" and either don't have a background or the proof itself. Like, it's fine if it works on your end, that's great, but nowadays people need to see proof by themselves to really believe ya

[sacred junco]

Then what you've said is less than what I interpreted.

[sturdy violet]

Like, it's awesome if ya did it, it's just that there isn't too much tangible evidence you truly did

[sacred junco]

I'm not unaware of the kind of epistemic bubbles various communities form.
And, I've even given a kind of justification one might use to affirm the usage of these dismissive heuristics constituting that bubble.

What I've noted, however, is that outright dismissal and condescension are NOT justified.
And I've even given a template of how one might respond to their sense of skepticism in a more ideal manner.

[sturdy violet]

I'm not trying to be skeptical, I'm just saying that you'll need a proof if you want to assert a theorem is correct

And the better way to do that is to publish it to arxiv to get it dated and properly assigned as your thing

[runic token]

^^

the best way to do anything here is to post on arxiv

[sacred junco]

It's unfortunate that the actual question I asked has been spoken over in this way.

At this point, it seems appropriate to not continue this conversation here.
This is gone into a broader discussion about pedagogy and math culture, which I'm fine with but I think that's probably out of scope for this channel.

The question I asked regards motivations for why people might try to solve these problems of how to write terms as sums of powers.
BUT "warring problem" was enough of a search term to fall down a rabbit hole regarding "additive basis" as a more general concept.

I guess my question now is why do people care about "additive bases"

[sturdy violet]

Fine, but if ya feel like we ran over some arguments, might be because I don't really get high English, too fancy for me

[sturdy violet]

Also a reason you might want to solve it is just to progress maths in general

No real application for it sometimes, it's just a cool new thing that might or might not be useful to prove other cool new things

It also bugs people if they aren't sure you can really do something simple like that so another reason is that

[sacred junco]

I'm not really sure what "high English" is here.
I would presume that if people are going to be elitist and try to justify that in a discussion on number theory, they would be able to understand the words I've said.
I'm not using like esoteric terms like "a-series of time" or "phenomenology".

[sacred junco]

Right.

I guess I was looking for like situations where people apply the concept of an additive basis to other problems in math.
Or like how the solution of various summation problems might be expected to inform other areas.
Or if there was like a broad family of techniques people were using.

[sturdy violet]

I mean using words that me as a non-native English speaker am unaware of. Like, I can speak formally, not super formally tho

[runic token]

nobody is being elitist here

[sacred junco]

Okay. That's fair.
I'll try to be more mindful about that.

[sacred junco]

I feel like I've argued how people are being elitist.
I think that people here just think that it's justified.
I disagree that it's justified.
I've at least argued better ways to go about handling that elitism.

I don't know why you feel like people are not being elitist here.
My worry is that this will go out of scope from the #elementary-number-theory channel.

I need to change gears, but if it's something you or someone else wants to talk about, maybe another channel is better at a later time.

[inner anchor]

On hilbert-waring itself, i know that there are a few different proofs which are all quite interesting by themselves

Iirc, hilberts original proof is based on funky polynomial identites, and there is a proof also based on more analytic techniques (the circle method)

I also recall having seen an other type of analytic proof which i cant recall much about

I think nathansons multiplicative number theory talks about the problem in detail

[sacred junco]

Thank you!

I gleamed the wikipedia page, but it doesn't go in depth.
Thanks for more search terms.

[inner anchor]

A thesis which contains an improvement of hilberts original proof refers to an article by ellison in the american mathematical monthly

Nathanson doesnt talk about the original proof, so if that interests you it might be worth checking out

[sturdy violet]

I'm working with a polynomial with variable terms (namely $x^3 - ax^2 + 4ux - nu$), how would I figure out in what cases this polynomial has integer solutions?

[sterile pumice]

Duhon

[sturdy violet]

Ig I could use diophantine equation techniques but that's out of reach for me rn, so some pointers could help

[sacred junco]

@inner anchor so my proof proposed an algorithm for determining what the corresponding summed terms would be. After checking more instances, my algorithm fails.

I'm curious about some these analytic approaches and how they might use notions of periodicity, especially if they find a way to connect, say, periodicity with complex numbers to modular arithmetic.

I think by leaning into some techniques there, that might help me better articulate and save some aspects of my proof.

[hoary island]

Lets say I have two multivariate polynomials, $f,g \in \mathbb{F}_p[x,y,z]$ such that $f ; | ; g$ and they are both homogenous polynomials of degree $d, d+s$ respectively. Is there a method to determine the coefficient of a degree $s$ monomial in $\dfrac{g}{f}$ without directly performing the division/quicker than the division?

[sterile pumice]

ddxtanx

[bitter quarry]

Can someone help me on this:

[fervent crest]

Ok

[pine badge]

Say I have x = {1, 2, 0} and y = {-2, 0, 2} I want to find a function so that (1,-2) , (2,0), and (0,2). How could I find that function?

[torn escarp]

a few ways are, you could use lagrange interpolation or try to throw f(x)=ax^2+bx+c at it with the points plugged in and solve the system of equations (AKA invert the vandermonde matrix)

[pine badge]

Hmm, I don't know those methods 😅 .

I'll have to Google hehe

[torn escarp]

there are a ton more, it kind of depends on what you want it to "look" like

[pine badge]

I only want it to work for those three values

[torn escarp]

then what you specified is pretty much sufficient, you could write that as a piecewise if you wanted

[pine badge]

Ok, I'll try and invert the vandermode matrix I guess, thanks

[torn escarp]

yeah that will end up nicely with integer coefficients

[pine badge]

Ok I was lazy and found a Lagrange interpolation web app.

But this allows me to build the machine
a(n) = 3n + f(n*mod(3))
where f(x) = 3x^2 -7x + 2.

[sturdy violet]

So that 1 maps to -2, 2 to 0 and 0 to 2?

Tbh I'm wondering what Lagrange interpolation does

[pine badge]

It maps 1 to -2 , 2 to 0, and 0 to 2. There are web apps where you just input points and it gives you an equation and shows the graph. I'm not sure how it works either

[leaden swan]

Well you consider special functions f(i,x) such that f(i,x)=1 if x=i and f(i,x)=0 otherwise

So well P(x) will be
$\ \sum_{i} P(a_i) f(a_i,x)$

[sterile pumice]

Drake

[leaden swan]

Where a_1,a_2... are your points

The idea is if you plug say a_1 this reduces to P(a_1)

[leaden swan]

Well as i varies over the x-co ordinates of the points to be modelled

So say you have (1,-2) ,(2,0) ,(0,2)
Then
$\ f(1,x)=\frac{x(x-2)}{-1} \
f(2,x)=\frac{x(x-1)}{2} \
f(0,x)=\frac{(x-1)(x-2)}{2}\$

[sterile pumice]

Drake

[leaden swan]

So our polynomial will be
$(-2)f(1,x)+(0)f(2,x)+(2)f(0,x)$

[sterile pumice]

Drake

[leaden swan]

So yea that's how Lagrange interpolation works @pine badge

[leaden swan]

Which reduces to 3x^2-7x+2

[wooden glen]

If you want a periodic function, you can also just say f(x) = ((x-1) mod 3)·2 - 2. That way there's no need for a quadratic.

[summer jackal]

Could someone prove/explaine why this is true?(Solved)

[sturdy violet]

I'm not 100% on this but if you have
$$n = p_1^{a_1}p_2^{a_2}\cdots p_l^{a_l}$$
the number of factors of that number is given by
$$(a_1 + 1)(a_2 + 1)(a_3 + 1)\cdots (a_l + 1)$$

Now idk where the other things from the number of integer triangles came from really

[sterile pumice]

Duhon

[summer jackal]

thanks.thats exactly the problem 🤔

[blissful marlin]

is there a name for this theorem

[mossy sun]

not that i know of. just a consequence of the Mobius inversion theorem, though it's easy to prove from the simple definition of phi

[blissful marlin]

what does it say

like

i can't understand it fully

[leaden swan]

\phi(k/a) can be seen as number of elements in {x| x<=k, gcd(x,k)=a}(As in "After removing a factor of a,there is no common factor") so this is equivalent to the statement that if x is less than or equal to n then gcd(x,n) is a factor of n
@blissful marlin

[blissful marlin]

oh

[mossy sun]

yeah it's just counting the integers up to n by grouping them by gcd(n, x)

[fervent crest]

<@&268886789983436800>

[unkempt void]

This theorem is also pretty strongly linked to the theory of cyclic groups, for what it's worth

[torn escarp]

one kind of fun way to see it explicitly is write out the n fractions 1/n, 2/n, 3/n,..., n/n and reduce them. Then the number of times d appears in the denominators is phi(d), and since there were n fractions to start with the sum of phi(d) must all add up to n.

[blissful marlin]

nice

[narrow flint]

Hey guys, I have a question about this: he question is: If p and q are odd primes determine if 2^(pq-1) is congruent to 1 mod p*q
I thought maybe i use euler's thm to get 2 to the power of phi(pq) is congruent to 1 mod pq as the GCD of 2 and pq is 1
and then as eulers totient function is multiplicative
i can get 2 to the power of phi(p) * phi(q)
and since p, q are odd primes, then their totient function are (p-1), (q-1) respectively
so then I get 2^(pq-p-q+1) is congruent to 1 mod pq
and now im kinda confused as to where to go next, can you point me in the right direction? thx alot
also sorry about the bad format im new to this server

[fervent grove]

I'm not even sure if what you're trying to prove is true

have you tried any small examples?

[narrow flint]

yea the question is like to determine whether the statement is true or false

i checked the answers after being stuck on a while and answer is that the statement is false but i dont know how to prove it

[leaden swan]

Well substitute p=7,q=11

[mossy sun]

to prove something is false all you have to do is write down and check a counterexample, which you've done

[obsidian saddle]

What are Vieta’s formulas useful for?

They give you a relationship between symmetric functions on roots of a polynomial and the coefficients of the polynomial

But why do we want this. Also does this extend to power series?

[narrow flint]

Ok, thank you

[stiff rivet]

one use i can think of is over local fields, it gives you a very powerful method to see if a polynomial is reducible

[stiff rivet]

probably no

[unkempt void]

It wouldn't really make sense for power series since the product of roots needn't converge

[obsidian saddle]

Yes but I was wondering if under stronger conditions if it could be applied

[obsidian saddle]

Also thank you

[umbral bridge]

This is niche, but it is a common question in competition math

[obsidian saddle]

It doesnt seem too niche for what Lochverstäkers response says

[umbral bridge]

I meant to say my case was niche

competition math

sorry for not clarifying!

[obsidian saddle]

No worries

Im not the best at english

[green linden]

Guys I understood the first 2 solutions we will get. But could anyone please explain how we got that third and fourth solution? (and also why we refer it to as only the third solution?)

PS: Please ping me if someone answers

[west glade]

that looks pretty wrong

let's ignore the abuse of notation in saying that x^2+ax+1=(x-a)(x-b) even though with the second a they actually mean something different

what they want to say is that because 3*3=9 mod 9 there can be solutions to x*y=0 mod 9 without x or y being equal to 0 which is how we usually solve these types of equations

but if x=3-a and x=3-b then 3-a=3-b and a and b have to be equal which isn't always the case

let's now take a look at their example. we see that x^2-2x+1=(x-1)(x-1) and so a=b=-1. from this we get the solution x=1 and x=3-(-1)=4

the extra solution we get from x=6-(-1)=7 because we also have 6*6=0 mod 9

and (I think the last) other such product is 3*6=0 mod 9

[green linden]

Where did you get the x = 3-(-1) from?

[west glade]

so a complete case analysis would be: see that (x-a)(x-b)=0. then we have one of the following:
case 1: x-a=0, x-b=something
case 2: x-b=0, x-a=something
case 3: x-a=x-b=3
case 4: x-a=x-b=6
case 5: x-a=3 and x-b=6
case 6: x-a=6 and x-3=3

that is the form x=3-a with a=-1

because we have x^2-2x+1=(x-1)^2=(x+(-1))^2=(x+a)^2 with a=-1

[green linden]

Could you explain case 3 and 4?

[west glade]

that corresponds to 3*3=0 mod 9 and 6*6=0 mod 9

[green linden]

so why can't we create a case for 9 as well. cause 9*9 = 0 mod 9?

[west glade]

well 9=0 mod 9 so we kind of treat 9 as 0 already

[green linden]

oh ya right

[green linden]

so this way we have 6 cases

[west glade]

unless I missed one, yes

[green linden]

But the question wants us to prove that there are THREE solutions

[west glade]

not all of these cases will give solutions x (because for example in case 3 and 4 a and b would have to be equal)

[green linden]

look

[west glade]

tbh I'm not sure that claim is true

their proof certainly doesn't work

[green linden]

But how do we know that a and b aren't equal?

[west glade]

well we don't. sometimes they will be equal and sometimes they won't be

[green linden]

So how would you prove this?

[west glade]

we have the two cases a=b and a!= b. for each of these we have the 6 cases listed. go through all of them and see which ones give a solution

and which ones maybe give the same solution

I gtg now, sorry

[rain pilot]

Excuse me
I'm thinking of a problem, about integer roots of the equation m! = n² - 1. May someone tell me the name of this problem please. Thank you.

[west glade]

this is called brocard's problem

it is open whether there are infinitely many solutions (n, m). so far only three solutions are known

[rain pilot]

Thank you

[arctic crane]

The sum of all fibonacci numbers is -1 mod 11 because 100/9899 = the sum of all fibonacci numbers. Can someone show a counter example proving me wrong.

[torn escarp]

the sum of fibonacci numbers is divergent

[arctic crane]

but any fibonacci number could be found in that fraction which is an infinite series (nth fib num)/100^n which under mod 11 is congruent nth fib num. Example the fifth fib num would be 5/100^5....which is congruent 5 mod 11.....so it contains the sum of all fibonacci numbers under modulus 11.

[runic token]

the argument for the sum of all fib #s being -1 is as follows: $1 + 1 + 2 + 3 + \dots = x$, $1 + 1 + 2 + \dots = x$, so $1 + 2 + 3 +\dts = 2x$. then, $x-1 = 2x$, thus, $x = -1$. this is divergent sum renormalization, and it is not equal to the sum

[sterile pumice]

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

[runic token]

look it up if you would like to know more

[umbral bridge]

This is similar to the sum of all natural numbers being -1/12 right?

Aka ramanujans sum

[trim cedar]

How can we prove that the sum and product of 2 algebraic numbers is algebraic

[north pagoda]

have you tried constructing a polynomial they might solve?

[stiff rivet]

this is not super easy for product iirc

||if a, b algebraic, then F(a, b)/F is finite and thus algebraic||

this is the usual (easier) way i think

[north pagoda]

hence why i'm asking whether they tried it

[stiff rivet]

now they have two approaches and it is worthwhile trying yours first

[trim cedar]

Constructing what polynomial?

[robust dirge]

this isn't elementary tho

[trim cedar]

Whats F

[north pagoda]

...a polynomial that the sum solves, and a polynomial the product solves

you know the definition of "algebraic", yes?

[stiff rivet]

say F are just the rational numbers in this case

[trim cedar]

Thats basically solves the question. Thats what i am not able to do

[north pagoda]

well, have you tried constructing one for the sum?

let's say x₁ and x₂ are algebraic, so they solve polynomials P₁ and P₂ with rational coefficients, respectively. x₁ solves P₁ and x₂ solves P₂. Can you construct a polynomial (using P₁ and P₂) that x₁ + x₂ solves? can you explain why it has rational coefficients?

"solves" of course means P₁(x₁) = 0, P₂(x₂) = 0

[trim cedar]

I have tried to find in terms of P1 and p2. But i wasnt able to.

Anyway i will try again

[trim cedar]

We can say integer coefficients instead of rational

[arctic crane]

The sum of all natural numbers mod 11 is congruent this fraction 100/9801....which means it is congruent 0 mod 11.....under congruences things become cyclic.....irrational numberes even contain repeating sequences....square root 2 mod 7 is 0 even though it has two roots 3 and -3.....maybe because they sum to zero.

[stiff rivet]

what

[narrow flint]

Hey, I am currently doing an elementary number theory course and I find that although I understand the proofs of theorems and how everything works, when it comes to problems I often get stumped or is extremely inefficient at doing them. Does anyone have any advice for me? Thank you for your help (also please reply to this message if you have a piece of advice so I can locate it better, thx!)

[arctic crane]

sorry the sum of all natural numbers mod 11 is 1/0.......with e and pi you also get a division by 11.....

[stiff rivet]

[stiff rivet]

inefficient? do you mean you do more work than the suggested solution? if so, i think this is normal and nothing to worry about
if you can't solve problems at all, then all i can suggest without more information is to practice more

[raven radish]

Gonna +1 what Lochverstärker said. It's one thing to be able to fully comprehend a proof, but it's another thing to try and prove it yourself without help. Understanding is already half the battle though, so you can do it!

[mossy sun]

are you the guy who posted on the project euler forums?

I thought about replying there but didn't go for it

basically this feels like gibberish

are you able to explain a little more in detail what it is you're talking about?

[stiff rivet]

i'd rather we only talk about mathematics in this channel

[arctic crane]

yeah....welll maybe it is gibberish....but I dont understand what is wrong with my logic

[mossy sun]

@arctic crane you can dm me briefly, I'm willing to discuss this with you for a bit.

[umbral bridge]

@mossy sun can we make a gc, I’d like to talk about it as well

[mossy sun]

I'm unable to because none of us are friends

[umbral bridge]

I’ll send requests

@arctic crane

[narrow flint]

Hey, I was wondering regarding the uniform step method in solving magic squares how would I actually get the 6 constants so as to solve for x and y, do I just have to make sure they satisfy the condition that cf-de is relatively prime to the length/height of square and that each constant except for the starting location are relatively prime to the dimension of the square, and the integers are arbitrary themselves?Thanks for your help! (pls reply to this msg if you have any advice so I can see it. Thank you alot!)

[somber lagoon]

@paper saffron are you the guy who asked this question last Wednesday in help-3 channel?

Anyway there is an article regarding it, theorem 3.1

[somber lagoon]

Sorry pinged the wrong guy, should be @indigo oar

[indigo oar]

ah I see

[rich kite]

we know that these are the remainders of dividing 2^n and 6^n by 7

suppose that

which means

how does this imply that $S_n\equiv 2^{n+1}+3\cdot 6^{n+1}+3\pmod 7$?

[sterile pumice]

DarQ

[rich kite]

in particular, I want to know what this has to do with anything

[fervent crest]

Multiply both sides of this by 3

[rich kite]

ye

I reasoned we can add 14S_n without changing the equivalence

[fervent crest]

Sure yeah same thing

[rich kite]

but this is literally the entire proof in the official correction

[fervent crest]

?

[rich kite]

I'm very confused what 5S_n has to do with anything

if from there you need to multiply both sides by 3 then why not multiply by 15 in the first place?

[fervent crest]

Yeah idk why they did that, because in mod 7 you have 1/5 = 3, so (6^{n+1}-1)/5 is already equal to 3*6^{n+1}-3

But I guess it's just making sure that both sides are integers before taking things mod 7

[fathom sierra]

I mean they're integers

They're just making extra suretm they have integers I guess

[fervent crest]

Yes

That's what I meant

[rich kite]

this is just HS level so we don't have equivalences between fractions

[fathom sierra]

I mean 3 is the inverse of 5 mod 7

1/5=3

There's nothing wrong with what's written though

[rich kite]

no, I meant it doesn't make sense to use the fact that $3\equiv 1/5 \pmod 7$ if we haven't covered equivalences between fractions

[sterile pumice]

DarQ

[fathom sierra]

You didn't see modular inverses?

[rich kite]

no

[fathom sierra]

That's very odd for some elementary NT

I mean just seeing 3*5 = 1 mod 7 is not that hard tbh

So that's the exam correction screwed up thing ?

I mean if you arrived at the same conclusion in another correct way there should be no problem

otherwise the examiners are ass

[rich kite]

afaik, I did everything correctly

at worst, I should deserver a nearly perfect mark

[fathom sierra]

So the question was like "here some S_n, show that S_n = blah mod 7" ? Just making sure

[rich kite]

tomorrow I shall see how much I got

[fathom sierra]

Yah

[rich kite]

yes, this is a follow up to the previous question

so it was just "show that S_n=blah mod 7" since we already knew what S_n was

thanks for the sanity checks btw!

I need to go rn

[fathom sierra]

cya tomorrow I guess

[somber lagoon]

I guess you are on your own… I understand the part of that article regarding your question now, but you need background knowledge about structure of finite abelian groups first, which is in most of algebra books, I personally recommend basic algebra written by Jacobson, it’s in chapter 3, however, after you have this background knowledge, to prove some results used in this article, you will need to read charter 2 and 4 of combinatorial number theory and additive group theory written by Alfred Geroldinger. This is too long a journey for me…

[west glade]

and probably way overkill anyway

[somber lagoon]

Maybe, but using a particular elementary method to solve a very special case where we already have references of the whole theorem, the full result, doesn’t satisfy me, and I haven’t found such elementary way anyway…

Anyway, the main obstacle will be the result of D*(G)=D(G) when G is an finite abelian group of rank 2, this result is stated and used in the article without proof, proof is contained in chapters 2 and 4 of that combinatorial number theory book, other than that, the article itself and algebra background knowledge won’t be too much a problem

[still flare]

An interesting question: what functions are those which preserve equivalence modulo n for all integers n?

This is to say that if x, y are congruent mod n then f(x) and f(y) are congruent mod n too, rather than f(x) = x mod n.

I'm going to think about this for a little bit

An interesting observation is that such functions form a ring!

[wooden sleet]

What in the world

I was just about to ask

Isn’t this asking us to characterize homomorphisms from Zn to Zn

[still flare]

Unfortunately not, no – that would be much easier though!

[wooden sleet]

What’s the difference?

[still flare]

The reason these are not necessarily homomorphisms is that they do not necessarily preserve addition, multiplication, identity, or zero.

A homomorphism would require f(x + y) = f(x) + f(y), for example, and this is an entirely different question

Aha, here's a start

Suppose f(0) = 0 for such a function. We can always start with a function g and set f(n) = g(n) - g(0) and this will be so.

Now x = 0 (mod x)

so f(x) = 0 (mod x)

so f(x) is always divisible by x

So we divide by x and repeat. Do you see my train of thought here?

I'm trying to figure out f(x) as a polynomial

Like, if:

$f(x) = a_0 + a_1x + a_2x^2 + \cdots$

Then:

[sterile pumice]

Boytjie

[still flare]

$f(x) = a_0 + x\left( a_1 + x\left( a_2 + x(\cdots)\right)\right)$

[sterile pumice]

Boytjie

[still flare]

So what I'm trying to show here is that if we "mutate" f(n) by taking away f(0) — which I think of as a_0 in this expansion — we really do get x times something

So it's looking a lot like these functions are just polynomials

Now all that's necessary to show that these functions really are polynomials is to show that eventually, if we keep repeating this process, we will get the constant zero function

I will now think about this

Do let me know if this doesn't make sense

[wooden sleet]

I don’t know how you got to this

Ok wait first of all these functions are defined on the whole Z right

[still flare]

Right so our assumption is that f(n) is a function such that, whenever a = b (mod m) we have f(a) = f(b) (mod m) right?

[wooden sleet]

And x represents an element of Z, not an equivalence class

Right, right

Hmm

[still flare]

And yeah, sorry I didn't define this explicitly but I'm assuming that f : Z -> Z indeed

So x is just any number, I'm using it generically

x = 0 mod x

this hopefully is clear!

[wooden sleet]

Right I get that part

[still flare]

so by assumption, f(x) = f(0) mod x

and I assumed that f(0) = 0

so indeed f(x) = 0 mod x

[wooden sleet]

Oh we’re assuming it’s true, oh yeah you said “such a function” ok I see lol

[still flare]

Right yeah perhaps I should've put more emphasis on that

So the reason I wanted to do this is because like, if you have a polynomial p(x), how do you work out the constant term? Well it's just p(0) right?

So if f(0) = 0, it kinda looks like a polynomial (my hunch) with no constant term

And if it really is a polynomial, well x always has to divide f(x)

[wooden sleet]

Yeah I mean you could also think of it like

If there’s no constant term, everything has an x attached to it

So of course x divides f(x)

[still flare]

Yeah exactly

[wooden sleet]

But here’s my question, couldn’t you do f(x) = x + 2, and that preserves equivalence because it’s just adding 2 to both sides?

That has a nonzero constant

[still flare]

Yeah this is what I'm saying

so like, we have this function f(x) = x + 2

f(0) = 2

so let's define this new function, call it g(x) = f(x) - f(0)

I'll leave it to you to check that g(x) also preserves congruence modulo n for all n

But now also g(0) = 0, right

So the argument that I used above actually shows the following

If f : Z -> Z preserves congruence modulo n for all integers n, then f(x) = a + xg(x) for some integer a and some function g : Z -> Z

What I'm thinking about at the moment is whether or not we can conclude that g(x) preserves congruence modulo n. My thought rn is that it doesn't necessarily.

[wooden sleet]

Hmm

[somber lagoon]

Yeah, let g(n)=n when n doesn’t equal 0, g(0)=1, g doesn’t satisfy your condition, but f(n)=ng(n)=n does

[still flare]

Wonderful counterexample ty

Well, this problem is very hard then

Oh actually in fact, we can choose g(0) to be whatever we like

[somber lagoon]

No

[still flare]

No we can

If f : Z -> Z preserves congruence modulo n for all integers n, then f(x) = a + xg(x) for some integer a and some function g : Z -> Z

[somber lagoon]

g need to satisfy g(m)=g(m+k) mod k for m isn’t divisible by k

[still flare]

Why is that?

[somber lagoon]

Because mg(m)=(m+k)g(m+k) mod k for any m

[still flare]

Right, I must admit I'm still not seeing why what you're saying follows?

[somber lagoon]

Property of f

[still flare]

Yes, so why does this mean g(m) = g(m+k) mod k?

We can't just rid ourselves of that factor of m

[somber lagoon]

Sorry not m isn’t divisible by k

Should be gcd(m,k)=1

[still flare]

Yeah so in fact this is for very specific m, right

OK

[still flare]

Now observe that from this, since f(0) = a, we can actually choose g(0) to be whatever we like, and still get a valid expression for f

[somber lagoon]

Yeah

[still flare]

So if we want to look at these functions, we really need to look everywhere but g(0)

which makes things quite complicated

I'm not sure how to approach this

[somber lagoon]

Yeah
f(n)=a+ng(n)=a+bn+nh(n)
h(n)=g(n)-g(0), b=g(0)
So f is linear map plus nh(n)
h satisfies h(0)=0, n/gcd(n,x) divides h(n+x)-h(x) still complicated

[muted notch]

i writted 30 as 5 * 6=5 * 2 * 3 thus i figured out that there will be always a even number

and i stuck

idk how to prove that there will be number that is divisible by 5 and by 3

[fervent crest]

For mod 5 the hint is fermat little theorem, for mod 3 you can use fermat little theorem as well or write down all squares mod 3

[heady basalt]

A variant of this problem : show that mn(m⁶⁰-n⁶⁰) is always divisible by 56786730 for every m,n∈ℤ

[fervent crest]

The only hard part of this problem is prime factorization

[dry urchin]

for the definition of modular forms, why is the growth condition nessecary

also it seems to follow from the automorphism condition which seems kinda cool

[muted notch]

@fervent crest i recently started number theory, in my book there was a task called

and it was easy to solve for me, but this one is new for me because of two variables

but the fermat theorem i will later learn in book

i need another hint how to do this task

[west glade]

powers of 5 are small enough that you can argue with fermat without actually "using" fermat

i.e. you could just calculate them

not sure if there is a proof which doesn't in some form use that m^4=1 mod 5

[muted notch]

Did you mean that i need somehow to use that m=5k and n=5k?

to prove that it is divisible by 5?

[west glade]

well how did you prove this one

[muted notch]

m(m+1)(m-1)(m^2+1)

three consecutive integers will always be divisible by 6

for (m^2+1) i just added (m-2)(m+2)

to add five consecutive integers and it will always be a divisible by 5

[west glade]

added?

but ok yeah I guess this doesn't use m^4=1 mod 5 I think. maybe hidden somewhere

[muted notch]

m^2-4+4+1

is (m-2)(m+2)+5

[west glade]

yeah so what you meant to say is that you expanded m^2+1=(m-2)(m+2) mod 5

anyway not important

[muted notch]

because i got on the final m(m-1)(m+1)(m-2)(m+2) + 5m(m-1)(m+1)

and it will be always divisible by 5

my book did it on different way

let m=5k

5k,5k+1,5k-1 then m, m-1,m+1 is divisible by 5

if m=5k+2 or m=5k-2

then m^2+1= (5k +- 2)^2+1=5(5k^2+-4k+1)

+- is plus minus im still learning discord

[west glade]

essentially a bunch of casework. well you could also do that casework for your other problem

but well quite a bit more cases

[muted notch]

i got confused on above problem because of two variables

[west glade]

use m^2+n^2=(m-2n)(m+2n) mod 5

[muted notch]

how that can be equal?

[west glade]

(m-2n)(m+2n)=m^2-4n^2=m^2+n^2-5n^2

[muted notch]

did you forgotten to add +5n^2?

[west glade]

forget? wdym

-4n^2=n^2-5n^2. I just wrote it in a more convenient form. and 5n^2 is always divisible by 5

[muted notch]

yes but m^2+n^2=(m+2n)(m-2n)=(m^2+n^2-5n^2)

in the last equation it will not be equal to m^2+n^2 if you don't add +5n^2?

[west glade]

that's why I said mod 5. Do you know what mod 5 is?

[muted notch]

i think that it is dividible by 5

the remainder is 0

[west glade]

no. a=b mod 5 means that a and b have the same remainder when you divide them by 5. equivalently, a-b is divisible by 5

so here we have m^2+n^2=(m+2n)(m-2n) mod 5 because m^2+n^2-(m+2n)(m-2n)=5n^2 is divisible by 5

[muted notch]

i think i got it. thanks @west glade

sorry but im completely new to number theory

[west glade]

no need to apologize

[split oasis]

Suppose I have $a^b = 3 \mod 4$ where a is prime, I need to show $a = 3 \mod 4$.

[sterile pumice]

Scerball

[split oasis]

Does anyone have a hint?

It's easy to show $a \neq 2$ and $b \neq 0$ but where do I go from there?

[sterile pumice]

Scerball

[fervent crest]

What are the possibilities for a mod 4

[west glade]

if a=0, 1, 2 mod 4, then what is a^b mod 4?

[ionic pier]

Well, you’ve done the first step, which is to show that a is not 2, but then a is either of the form 4k+1, or 4k+3. If it’s 4k+1, then a=1 mod 4, and therefore a^b=1 mod 4 for any b. So the only way a^b to be 3 mod 4 is to have a=4k+3 and b=2m+1