elementary-number-theory

[sacred junco]

Sorry for the ping, confused my thoughts lmao, one sec

@sacred junco help pls

[sacred junco]

Hint: try contradiction, and multiply all positive elements mod n together

[wooden glen]

I would say try proving the contrapositive.

[sacred junco]

Exactly

It works out the same way

[sacred junco]

so which a would you pick from the set {1,2,...n-1}

[sacred junco]

pick a = (n-1)! ?

[wooden glen]

If you're assuming that n is composite, there are some numbers in the range that behave specially ...

[sacred junco]

its divisors?

[wooden glen]

Try them.

(b) looks brutal, though. If you know the name of the concept you can google for the smallest qualifying n; it turns out to be in the several hundreds.

[sacred junco]

i think i saw an example in wikipedia

341 prolly

[wooden glen]

Yes.

[sacred junco]

it's a pseudoprime

anyways if a=(n-1)! then a^n-1 is congruent to 0 mod n

but 0 isnt from the set {1,2..,n-1} so i dont think that works

Distribute the exponent to each factor and see what happens, since the problem has us assuming each one of those factors is just one, then...

so let's say n=k*l where k,l are proper factors. k^n-1 is congruent to 1 mod n and l is congruent to 1 mod n then kl is congruent to 1 mod n. This contradicts it being congruent to 0 mod n?

Poggers, you did it
I think you can verify that yourself right
But I agree with you

Take care with how you write it up

hmm i wonder if i read the theorem correctly

Wait I might have done something very silly idk though

looks ok

so the theorem is for all a belonging to {1,2..n-1} if a^n-1 is congruent to 1 then n must be prime

suppose for contradiction

for all a belonging to {1,2..n-1} if a^n-1 is congruent to 1 then n is composite

(for some n)

then n=k*l and we plug in a=k and a=l so that k^n-1 is congruent to 1 and l^n-1 is congruent to 1

so kl^n-1 is congruent 1 when it should be congruent to 0

Right ok it is fine whew

hope so

[sacred junco]

i think it's for some a if you're talking about the contrapositive

like

for some a in the set {1,2..,n-1) if n is composite then a^n-1 is not to congruent 1 mod n

[sacred junco]

The negation of "for all n, if S is true for all of these a, then n is prime" is "there is an n, so that S is true for all of these a, and n is composite"

So yeah I guess haah

Wait no fixed it

It is just some n in the assumption for contradiction

so is my proof wrong lol

No it works for assuming only "some" n as you did it
The wrong way to do it would be if we chose a concrete value for n that gives a contradiction

whew

do i need hensel's lemma for this

solve x^2 is congruent to p to get 1 and -1

and lift those solutions

Damn I forget whether Hensel's lemma not only lifts uniquely (thats true) but also whether lifting gives all of the solutions

Here I think you don't have to worry about that so much tho since there's another argument possible maybe? Try playing around with the equation and see if you can factor it nicely

well p^n can divide x+1 or x-1 or but not both

it doesn't have to divide either of them tho?

cause if x+1=p^3 and x-1=p^n-3 then p^n doesn't divide either but divides their product

I think you can show that such factors could never differ by just 2 (p is odd)
But I think for a more elegant proof your idea with Hensel's lemma is good if you can find something to back that up cause again idk whether it gives you all sols

Well actually this is plenty elegant lol

ok so p^n divides (x+1)(x-1)

it can't divide both factors cause then p^n divides 2

how does that help?

From what you said before you get that both of the factors have to be multiples of powers of p
So then contradict by noticing that they differ only by two

do they have to be powers of p though

Fixed it lol

im sorry what assumption are we trying to contradict

Oh sorry I meant to assume for contradiction that x is neither 1 nor -1

we already know those are solutions

it's saying there are no other solutions

Ye that's the point, if you assume there is yet another and get a contradiction, then you're done

let's call it a and a is neither 1 nor -1

p^n divides (a+1)(a-1)

then what

p divides (a+1)(a-1) ?

and then p divides only one of them?

so a is congruent to 1 or -1 mod p

that just says it's of the form 1+pt or -1+pt t isn't necessarily 0

Right hm I was hoping that way would work out but I will have to do the way I was thinking

Since (a+1)(a-1) is a multiple of a power of p, if that multiple is not just 1, then it's in the group of units so we can just remove it since 0 is on the other side

And now we have a power of p congruent to 0

Lost my train of thought whoops

wonder what this dude's saying

Oh damn it was way simpler than I thought lol

his last step looks iffy

Since the other factor isnt divisible by p you can just remove it since 0 is on the other side, and then it's immediate from tbere

it says x is of the form 1+pt or -1+pt. Why is t necessarily 0?

there are numbers of the form 1+pt in the range 1 to p^n

What do you mean

This proves why t is necessarily 0 mod p^n

i get it's 0 mod p

i dont get why it's 0 mod p^n

p is a prime so it has to divide at least one of two factors in a product it divides

And one of those in this case is actually not a multiple of p at all

So we assumed from the start that p^n divides (a+1)(a-1), but now we can say wlog that p does not divide a-1

So (a+1)(a-1)=0 mod p^n right

We can multiply the inverse of (a-1) on the right since it exists, it's not divisible by p so it cannot be divisible by any factors of p^n

Hence (wlog) a+1=0 mod p^n

And there ya go

Lmk if anything needs clearing up or is messed up

so if p doesn't divide x+1 then neither does p^n, so p^n is forced to divide x-1 ?

Yeet

nice

do i solve this mod9 and mod5

and combine them using chinese remainder theorem

Sounds great

sounds big tho

Dont you think so

Y 😭

like let's say mod 9 gives 2 solutions and mod 5 gives 2 solutions

do i have to solve a linear congruence system

4 times

You can precompute the mapping for crt

But wait yeah I get what you mean

Probably 😭

[sacred junco]

does the polynomial having degree 3 imply anything

Or just find the at-most 3 sols for each given by Lagrange+Hensel

i know it's at most 3 for mod p

Yeah that

but it's mod composite so idk

Powers of primes are governed by Hensel's lemma and I'm pretty sure lifting does give you all sols

this looks like a good time to whip out some for loops from my cs1 class

Lol

true but

3^2 isn't much trouble

just plug and chug

3^4 would've called for hensel

Yeah just go for it

Wait I hope you are precomputing the crt stuff cause otherwise there's a word for that, "self harm" 😂 @sacred junco

bruh what's precomputing

like ik there's a constructive formula

but that involves finding inverses

and using euclidean algo

Finding inverses is super easy for small mod

give me a multiple of 5 that is one more than a multiple of 9

right

no hensel's lemma im screwed

is f'(1) congruent to 0 mod 3 useful

did you get no solutions for the other one

oh didnt try yet

oh lol

hw due in 2 hours lul

[sacred junco]

not sure why but i'll take it

[jovial bison]

Having trouble figuring out how to mathematically explain properties of the floor function. I get it intuitively.

Show that $$ \lfloor x \rfloor + \lfloor x + 1/2 \rfloor = \lfloor 2x \rfloor $$

[sterile pumice]

Armani

[stiff rivet]

write x as some integer plus something in [0, 1) (why is this possible?)
consider the case something < 1/2 and the other case

[vernal ibex]

Any good and Easy to understand Intuitive Elementary Number theory resources please.

[prime gust]

Hey, I have just finished reading a book about elementary number theory and I want to keep learning about number theory. Does someone know what I should study next?

[stiff rivet]

what book did you finish? how much abstract algebra and analysis do you know?

[prime gust]

underwood dudley elementary number theory

I didn't study any abstract algebra and my knowledge regarding analysis is very poor. Do you have any book recommendations?

[wooden glen]

Your most promising ways forward would probably be either to continue with a general introduction to abstract algebra (much of which was historically developed in a quest to get a handle on Diophantine equations), or to brush up on analysis and then read complex analysis to get the prerequisites for analytic number theory.

In general, if the questions that interest you are sweeping infinitary claims about the aggregate behavior of, say, all the primes together, then analytic number theory would probably be the most immediately rewarding. On the other hand, if you want stuff that boil down to facts about concrete calculations with specific numbers or equations, go the algebraic route instead.

[prime gust]

Thanks for your advice!

[unkempt needle]

Hi, I am working on this problem. I proved the first half, but had a hard time figuring out the later half. I assume a^m = 1 mod p for contradiction, so a^n - a^m = 0 mod p. Then p | a^m or p | (a^{n-m} - 1). p|a^m is not possible because if so, p|a^n. I dunno how to show p|(a^{n-m} - 1) is not possible and how to use (p,n) = 1. Any hint would be appreciated

[wise badge]

does this even have any solutions?

[wooden glen]

That looks like a job for quadratic reciprocity

[prime sparrow]

If a^m=1 mod p for some m<n then WLOG we can assume that m divides n (because we can take a^{integer combinations of m and n} to get a^{gcd(m,n)}. From here we see that a must be a root of one of the cyclotomic polynomials of d where d|m but then d|n and d<n hence a must be a double root of x^n-1. Taking derivatives we see that a is a root of nx^{n-1} ie na^{n-1}=0 mod p. But since n is invertible mod p, we get a^{n-1}=0 mod p hence a=0 which is a contradiction

[unkempt needle]

Thank you! Though I am a little confused on why a must be a root of one of the cyclotomic polynomials of d and why a^{n-1} = 0 mod p implies a = 0?

[unkempt needle]

I seem to figure it out. Thank you!

[patent escarp]

Well I’ve been redirected here again. I’m trying to find all integer solutions to $n^{2}=\left(2xy\left(2x-y\right)\right)^{2}+\left(z^{2}\left(x-y\right)\right)^{2}$

[sterile pumice]

Chixen

[sacred junco]

idk but the implicit surface you get generally looks like some wacky pokemon

higher res uwu

[patent escarp]

wow

so

where on there are the integer solutions?

[sacred junco]

somewhere~~~ but the picture at least justifies there will likely be infinitely many
also we don't get the strong condition that usually leads to the formula generating pythagorean triples since everything isn't necessarily coprime. BUT following the steps of the proof you get something similar

Also I think it might be useful to write (x-y) as t because that transforms the whole thing into $(2x(x^2 - t^2))^2 + (z^2 t)^2 = n^2$

[sterile pumice]

zd

[sacred junco]

and also we must assume for nontrivial solutions that z and x-y are not zero anyways

Also the something similar I'm talking about is $\frac{2x(x^2 - t^2)}{n} = \frac{p^2 + q^2}{2pq}, \frac{z^2 t}{n} = \frac{p^2 - q^2}{2pq}$ or vice versa, with coprime integers $p$ and $q$ of different parity. We can't assign numerators/denominators to each other like we would if the left side were in least form too though of course

[sterile pumice]

zd

[patent escarp]

idk for what i’m using it for finding only coprime values would work fine.

[sacred junco]

like coprime values of $2xy(2x-y)$ and $z^2(x-y)$?

[sterile pumice]

zd

[patent escarp]

nvm I need all. I mistook something

[sacred junco]

kk cool

I was playing around with discriminants too and couldn't find much unfort

[patent escarp]

Also i’m so glad somebody has a way to attack the problem

I did write a brute-force program to find a lot of them and it did find a lot

[sacred junco]

niceeee

[patent escarp]

Just to pick one at random (20,6,77)

The only issue is that they seem random

(btw I’m using this because I found a way to transform solutions to this equation into near-miss solutions to the magic square of squares problem)

Is a pretty convoluted method but it works

like for (20,6,77) you get:

22946^2 | 20136248062 | 99113^2
19458919102 | 100807^2 | 29414^2
102473^2 | 13706^2 | 19797583582```

They bet big but they work

[sacred junco]

oh wow so what are the near misses supposed to be? no more than 3 non-squares in the magic square or something?

[patent escarp]

yeah

[sacred junco]

I see

[patent escarp]

But there is actually a €1000 prize (i think) for one with 7/9 or higher

other than the current known one

[sacred junco]

ooo

oh also whoops I wrote it wrong

$\frac{2x(x^2 - t^2)}{z^2 t} = \frac{p^2 - q^2}{2pq}, \frac{n}{z^2 t} = \frac{p^2 + q^2}{2pq}$ (and definitely not vice versa lol)

[sterile pumice]

zd

[sacred junco]

there we go

it looks possible to break down cases from here, but the casework could be hellish

at least at the end even if you don't have a comprehensive solution, the conditions you get will reduce computation time by a lot @patent escarp

aka considering cases whether 2 divides z, or 4 divides t, or p^2 divides z, p divides t, q^2 divides z, q divides t,... blah blah blah

because some of these must happen always for our nontrivial solutions

and also you know p^2 + q^2 divides n, p^2 - q^2 divides 2x(x^2 - t^2)

[patent escarp]

To be honest computation time wasn’t really an issue more so than the memory. Do you know a language that’s fast and doesn’t have rollover issues?

[sacred junco]

not sure wym by rollover but if you want to tinker with program memory then C is the way to go

java does hide less under the hood memory-wise than languages like python though so if you don't need to go nitty gritty with memory stuff that should be fine enough too

wait do you mean like the types you're using are running out of memory? I misinterpreted what you said I guess @patent escarp

in that case you can use something high level as long as you are working with a good type that has arbitrary precision

integers in python for example are arbitrary precision

there's also a rational type you can import that has arbitrary precision

[patent escarp]

Do you think python integer would be faster than java BigInteger?

[sacred junco]

honestly idk

[sacred junco]

btw how is this a solution just wondering

[patent escarp]

It was just a random one I picked from my list.

[sacred junco]

what are 20, 6, and 77 in relation to x,y,z,n?

[patent escarp]

$\left(2\left(20\right)\left(6\right)\left(2\left(20\right)-6\right)\right)^{2}+\left(77^{2}\left(20-6\right)\right)^{2}$

[sterile pumice]

Chixen

[patent escarp]

I put it in the list in the form (x,y,z) as finding n from that is pretty easy.

[sacred junco]

are you sure that's a perfect square

[patent escarp]

it was just in my list

I didn’t check

[unkempt needle]

I was looking through this. Could anyone explain a bit why because p, q are prime, x=qk, y = pk? (I can see after this, px=qy, but why?)

[sacred junco]

You said you could see it given px=qy right @unkempt needle

well a + px = a + qy definitely implies px = qy

Oh I misread, you mean that you could see it going in the opposite direction easier right? my bad

looking at px = qy, p has to be a divisor of qy due to the fundamental theorem of arithmetic. But it can't be a divisor of q since it's a different prime. So p divides y, likewise q divides x

so all that is left to show that the multiple of p or q is the same, k

[sacred junco]

even simpler, reduce mod p or q and examine

So anyway we have px = p(qk) = pqk = pqt= q(pt) = qy

and there you get k = t

[unkempt needle]

I see. tysm!!

[atomic fractal]

How to find the number of divisors any number has besides brute force enum method?

[wooden glen]

It is hard in general.

[atomic fractal]

I look through number theory intro books to get intuition behind my question. Why it is hard? What's the main obstacle in it?

[wooden glen]

The obvious way to count divisors is to factor the number, but factoring is believed to be hard.

[atomic fractal]

Got it.

[wooden glen]

This is not quite an impenetrable argument, because e.g. you can identify a number as composite in polynomial time (and so know that it has at least 3 divisors), and you can also quickly determine whether it is a perfect square (which tells you whether the number of divisors is odd or even) -- but it's hard to see how extensions of such trick could give you full knowledge of the number of divisors without also giving you a factorization.

[sacred junco]

Just buy a quantum computer and run Shor all day ez

Jokes aside Pollard rho is pretty cool

I think there's some upper bound above which other algos start being more efficient but iirc it's pretty solid up to quite large numbers

Just dont remember what exactly "quite large" is here lol

[hollow zenith]

this is for my abstract alg HW but this is more number theory than anything

so from the hint you get 1 + 8y + 16y^2 = 1

so 8y + 16y^2 = 8y(1 + 8y) = 0 (mod 2^n)

1 +8y is coprime to 2^n for n >= 3 so can we just say 8y = 0?

that feels wrong

[wooden glen]

It feels alright to me.

It implies that 4y == 0 (mod 2^{n-1})

which means there are only 2 equivalence classes mod 2^n that 4y can be.

[hollow zenith]

0 and 2^(n - 2) right?

which I can then sub back into the definition of x

[wooden glen]

2^{n-1} I'd say.

[hollow zenith]

wait what?

[wooden glen]

2^{n-2} is not congruent to 0 modulo 2^{n-1}.

[hollow zenith]

oh right I need to keep both equations in mind

[unkempt needle]

Hi, could anyone give me a hint about how to show if a = 1 mod p_i where p_i is different prime, so a = 1 mod p where p is the product of these primes? I can show it's true if there are only two primes, but I don't know how to generalize

[frosty schooner]

Try showing this:

Let p be a prime, and let q be a composite number which is relatively prime to p (i.e., p is not a divisor of q). If a = 1 mod q and a = 1 mod p, then a = 1 mod (pq).

If you can prove this, you can then use induction to finish the proof.

i.e., let q = p_1 x ... x p_n
and then let p = p_(n+1)

[unkempt needle]

I see. Thank you!

[frosty schooner]

Happy to help.

[prime gust]

Hey guys, can someone help me with a problem?

[formal minnow]

not unless you actually ask your question

[prime gust]

Honestly I don't really get the question itself

I do get the fact that if p does not divide a(i) for 1<=i<=p-1 then p obviously would divide a(i)-k for 1<=k<=p-1 but how can I show it?

Actually no I dont get the fact lol

[sacred junco]

How would you show for a_i not a multiple of p, that a_i is nonzero mod p? Well if it were zero mod p... I think you can finish that thought

Also try to rewrite the condition about differences as an equation mod p, for, say, some a_i and a_j

[prime gust]

okay,thanks

[main plume]

what's the largest prime number you can write where each digit or combination of digits is an increasing prime number starting with 1. So for example, 123719 is the largest I can think of.

Is this possible to solve? It could be infinite? Should I try to rephrase my question? I'm a bit rusty but just started thinking about this.

[cinder sigil]

Is there any way I can calculate the number of times a number between a and b is divisible by n or ends with n digit, without excessive brute-force looping?

I can find the number of divisible by for example doing (b - a + 1) / n (floor division)

And then for how many there are that ends with the digit we can do b / 10^(digits in n) (floor division)

But I will double-count occurrences here

[sacred junco]

what do you mean by "ends with n digit"? Like ends with n digits? So the whole number is at least n digits? Maybe something else?

[main plume]

Sorry the example I gave doesn't work becuase 12 is composite. So you would have 1,371,113 which is prime but 137,111,317 is composite.

[cinder sigil]

Hi! I mean that for example if n = 6 then 16, 26, 36, 46 ends with n

And if n=13 then 13, 113, 213 etc

[sacred junco]

Ahh I see

[main plume]

So my question is can you keep constructing primes this way?

[wooden glen]

The LHS is n(n+1)(2n+1)/6 which doesn't leave many options for making it a perfect square.

The factors in the numerator are coprime, so except for the 2 and 3 that get divided out, they all have to be squares themselves.

[inner anchor]

this is well known as the cannonball problem

the only nontrivial solution is like (24, 70)

[midnight folio]

How to prove that there are infinitely many primes of type 4k +1 without using congruence

[wooden glen]

"without using congruence" excludes pretty much all of number theory.

[opaque plaza]

How to prove gcd(3^a - 1, 3^b - 1) = 3^gcd(a, b) - 1
I obtained gcd(3^a - 1, 3^b - 1) = gcd(3^b - 1, 3^(a-b) - 1) by euclidean algorithm. But I'm not sure this implies that consequence.

[opaque plaza]

a and b are integer.

[ionic pier]

Is it $3^{a-1}$ or $3^a - 1$

[sterile pumice]

DVD_Koce_DVD

[opaque plaza]

gcd($3^a - 1$, $3^b - 1$) = $3^{gcd(a,b)} - 1$

[sterile pumice]

kr

[torn escarp]

yeah that's fine, doing a step of euclidean algorithm corresponds to doing it to the exponents, so that works

[opaque plaza]

so is this true?
gcd($x^a - 1$, $x^b - 1$) = $x^{gcd(a,b)} - 1$

[sterile pumice]

kr

[opaque plaza]

or it is true only if x = 3 ?

Wait, I think it must be true.

I lied

It's not true

4

[torn escarp]

what x did you find it to be false for

[opaque plaza]

4

a=3 b=6

[torn escarp]

show what you get

I don't think this is a counterexample

[opaque plaza]

nope i miscalculated

it's not 4085

4095

and i got

[torn escarp]

it's probably worth mentioning you can actually explicitly factor, like suppose a=n*g with g being the gcd(a,b)

$$x^{ng}-1 = (x^g-1)*\frac{x^{ng}-1}{x^g-1} = (x^g-1) *(1+x^g+x^{2g} + \cdots + x^{(n-1)g})$$

[sterile pumice]

Merosity

[torn escarp]

just an alternative perspective on it

this immediately proves their gcd must be at least x^gcd(a,b) - 1 because we know we can factor it out from both in this way

[opaque plaza]

It make sense for me

thanks for mentioning

thanks I love this algebraric view

[torn escarp]

yeah you're welcome

[topaz ridge]

is this a good definition for a prime number?

$p$ is prime iff $a \nmid p \ \forall \ a \in \mbb N \setminus {1, p}}$

[sterile pumice]

ryc for mod³

[topaz ridge]

(assuming 0 isn't a natural number)

[stiff rivet]

certainly p will divide p

[topaz ridge]

oh true

[stiff rivet]

if you include that, it works

you can write this same thing "better" by expanding the definition of \mid

$p = ab \implies a=1 \lor b=1$

[sterile pumice]

Lochverstärker

[topaz ridge]

oh interesting

alright tyvm!

[stiff rivet]

or actually even better is $p \mid ab \implies p \mid a \lor p \mid b$

[sterile pumice]

Lochverstärker

[stiff rivet]

so no reason to expand

i say better, because this definition works in more general rings (you dont have to care about this, if you dont know what a ring is)

[topaz ridge]

I see

I haven't gotten to ring theory yet but I know what a ring is

[stiff rivet]

ok, you can define "divides" in any ring just as in Z

and then use this definition of prime

and this will be useful at some point

[topaz ridge]

I can see why the definition I presented doesn't work since it is specific to the naturals

[stiff rivet]

one problem that would emerge with your definition already in Z is that both 1 and -1 divide every number

[topaz ridge]

so the definitions you presented make sense

[stiff rivet]

and in more general rings there are more such elements (called units)

so my second definition will be better

[topaz ridge]

I do know this

alright tysm for your help!

[abstract vortex]

Plz explain the last outcome ...

[sacred junco]

does the formula not remind you of some well understood progression ?

[abstract vortex]

@sacred junco No, if u remember suggest

[sick bridge]

Look up sum of geometric progression

[sleek cove]

look up en passant

[inner crest]

holy hell

[topaz ridge]

holy hell

[regal cloud]

can anyone help with this?

[sacred junco]

One way to represent the nonzero residues mod p is as plus or minus 1 up to plus or minus (p-1)/2, try justifying that concept to yourself and see if you can use that property here

[sacred junco]

For example working mod 3, the solution to 2n<1 would be 3, yes?

So explicitly it might be a good angle to bring another variable into this

We're solving an-rm < b in the integers with 0 <= b < m, and minimal n>1

And n determines r with respect to the other variables

Existence is guaranteed cause if a is a unit you can jump below b always
And if it's a zero divisor you can jump to 0 for example

Well for smallest n, looking at this as an-b<rm, r can only really be as big as m, maybe m-1, if we make a positive and restrict it also to 0<= a< m

Which is sufficient

Yeah the bound for r should be m-1

[leaden swan]

Just extended Euclidean?

[sacred junco]

Why would that work? If it did you'd have something in log time which is good

Failing to see how the bezout coefficient on a is necessarily minimal

[leaden swan]

This is a standard modulo inverse computation no?

Maybe iterate through all the possible solutions

That will still be log n

Or well there will be gcd(a,m) solutions

[sacred junco]

Increasing r in a loop and searching for the smallest existing n in 1 < n < (rm+b)/a would work I think right, cause the right side is only getting bigger so the first working smallest n you hit will continue to be the best n

So you don't have to keep looping, it will end when you hit that one first

and a should be reduced mod m beforehand of course

In the first few loops for large a that range might be empty but the second it's nonempty boom it's done

[sacred junco]

Aaaa there's probably a way to logic out when this range is nonempty as well?

Maybe not idk

But just an example for my mush brain, 1<n<(5r+2)/4 gives us upper bounds, taking floor, of 1, then 3 and we are done so n is 2

Does that work lemme check

4*2 - 2*5 = -2 what have I done 😩

Well it might not even work so 😭

[sacred junco]

Idk if it matters anymore but I fixed my thing, the smallest r such that the interval rm/a < x < (rm+b)/a contains an integer gives us our n, which is the smallest integer for x

And this should be equivalent to the original thing, starting with the same constraints of course

Doing this for the same example that didn't work last time works now: you get n=4 as the correct solution this time for m=5, b=2, a=4

As you said it might be the same as just looping naively though

@unique cave I'm curious about your problem, did you make any new insights?

[sacred junco]

Probably additive inverse like d = m-a mod m? I assume you don't mean multiplicative inverse because then for lots of a and m this problem doesn't have any solution

[sacred junco]

i've been struggling all night with this problem help

<@&286206848099549185>

[sacred junco]

<@&286206848099549185> dont wanna spam but i could really use some help

[sacred junco]

on her way to her grandmothers house jackie traveled three times as many miles by train as by bus she traveled four times as many miles by bus as by foot if jackie traveledd 34 miles in all how many miles did she travel by train

can someone please help me

[sacred junco]

<@&286206848099549185> help

[pulsar cloud]

for a very large prime p

where p is known ?

[sacred junco]

The exponent works mod phi(p)=p-1, and to be extra precise we can even check whether 2 is a primitive root or not depending on if we know enough about p to compute p-1 divided by prime factors

If not, we solve the discrete log problem for a primitive root giving us 2 and then multiply that by a in the exponent
I can clarify further if you're not familiarity with what I mean @pulsar cloud

I think at face value you probably can't solve it immediately without working with some assumptions for p, mostly because you could have zero divisors in the exponent sometimes and sometimes they are different

Could be totally wrong though

Wait lol... Am I overcomplicating this? Will all solutions to a=157a mod p-1 be exactly those to this equation?

Ah wait nah it's what I said before, there are cases you might have where a isnt 157a mod p-1, but then both multiplied by (p-1)/ord(a) gives you equality because they could both multiply to zero maybe? Aaah idk

[sacred junco]

Forgot to post this but I thought of an example and I was correct, you do have to consider the order of 2

Basically this equation should be equivalent to (p-1)/ord(2) a = (p-1)/ord(2) 157a mod p-1

@pulsar cloud

A nicer way of writing it is $156a \frac{p-1}{ord(2)} \equiv 0 \pmod{p-1}$

[sterile pumice]

zd

[sacred junco]

Which turns into $156a= (k)ord(2)$ for some integer $k$, and now this should be easy to solve once we know $ord(2)$

[sterile pumice]

zd

[sacred junco]

You just look at common factors of 156 and the order of 2 in Z/pZ

And fill in what's missing times any integer

Basically lcm(156, ord(2))/156 times anything is a solution

[hollow zenith]

is there any accepted notation for the zero function

much like how id is accepted for identity?

[wooden glen]

"0" will suffice in many contexts.

[fathom lagoon]

If I want to change congruencies like this ^
+, - is normal
*, / affects the mod?

[fiery iris]

p x k + 2^a = 2^157a
px k = 2^a(2^156a-1)
p cannot be 2^a or any multiple of 2 infact. and so i’d expect m* p = (2^156a-1)
maybe try find a value of a where m = 1 and p is a mersenne prime

@pulsar cloud

[naive drum]

Yes. Consider the definition of congruence...

$2y + 2 \equiv 0 \mod 8 \ \iff 2y \equiv -2 \mod 8 \ \iff 2y \equiv 6 \mod 8 \ \iff 2y=6+8k \ \iff y=3+4k \ \iff y \equiv 3 \mod 4$

[sterile pumice]

mandelbruh

[vagrant maple]

its -24

bruh

[sacred junco]

no it's -80085 @vagrant maple

[sturdy plaza]

hi how do you perform modulos for large numbers? The number are too big for a regular calculator

[gilded tinsel]

are you tryinh to calculate 1900^13?

for something like worlfram alpha, its trivial

so really it depends what u mean by "calculator"

but if its something like a casio

then use ur mod laws

think about which ones apply here

[sturdy plaza]

yeah i meant during an exam, so we're only allowed to use simple calculator

im not sure which rule to apply here... can you give me a hint

[wooden glen]

(Is that problem using RSA in ECB mode? Boo!)

[wooden glen]

One way to phrase the rule you need is: ab mod n = (a mod n)(b mod n) mod n. So you can take mod 2537 at intermediate steps in multiplying together your thirteen 1900s, every time the numbers threaten to become too large to handle.

[hollow zenith]

Say we have $\sigma(n)$ is the sum of the positive divisors of $n$. I need to characterize the integers that this occurs for. My claim is that $\sigma(n)$ is odd if and only if $n = 2^r k^2$ for some natural numbers $r, k$. I have the reverse direction but I am struggling to show the direction presuming that $\sigma(n)$ is odd.

[sterile pumice]

Spamakin🎷

[hollow zenith]

I could try contrapositive, i.e. suppose n != 2^r k^2

but I got stuck with that also

nvm I think I got it

[sturdy plaza]

yes it is

[regal cloud]

could anyone help with this?

[supple palm]

how do you think you should start the problem

[regal cloud]

are you talking to me

Im stuck on 3.2(b)

[supple palm]

oh err yes sorry i should have pinged

right so i think a good start would be to consider the prime factorisation of m
and where these primes might appear in the product
$(m-1)(m-2)(m-3). . .(2)(1)

note that having m≠2p and m composite (which is essentially saying m≠1p)
mean for any prime factor p of m we have m>2p>p

[regal cloud]

Hmm i see

I noticed this

And the fact it led to two cases

It is noted we are talking about m^2 btw i dunno if u noticed

@supple palm

[supple palm]

yep

[sonic dawn]

How do I use the well ordering principle for this? If the well ordering principle only works for subsets of the nonnegative integers and they want me to prove this for ANY integer n

[wooden glen]

If n is negative then k=42 always works.

[sonic dawn]

why 42

would zero work as well

[wooden glen]

No, because zero is not a positive integer. 42, on the other hand, is positive.

[sacred junco]

I'm trying to explain why the least remainders algorithm at least sometimes factors two positive integers in fewer steps than Euclid's algorithm. I haven't proven this, but it looks like the remainder for the nth step in LR is always equal to or less than the remainder in the nth step of Euclid's. And when the remainder gets to be smaller in LR, it's because we've sort of skipped a step compared to Euclid which happens when the Euclid remainder is large.

Is there more about this I might want to say?

[pliant lily]

I'm trying to prove that any perfect square ends in one of 22 different possibilities, that is, it can end in two digit numbers (00, 01, 04, ...96). I'm given as a hint that x^2 is congruent to (50 + x)^2 (mod 100) and x^2 is congruent to (50-x)^2(mod100) but I don't see where that came from nor how that helps. Any ideas?

[sand iris]

"If a,b ∈ N are coprime, and ab is an nth power, then so are a and b" Is anyone able to explain this to me? Im so confused, idk what the theorem is trying to sa

[pale fjord]

If $k,n$ are positive integers satisfying $k>n$.
Prove that the equation $x_1^2+x_2^2+\dots +x_n^2=kx_1x_2\dots x_n$ has no positive integer roots.

[sterile pumice]

erictheeonicpizhao

[wise badge]

is there a formula to find the p-adic value of the factorial of some number? for example suppose p = 3, then how would I find v_3(n!)?

[sacred junco]

several people are typing
It does exist and it's pretty useful

I bet it's what troposphere will be describing rn

;)

[wooden glen]

You want to find $\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor$. Those floors look horrible, but it turns out that the \emph{difference} between this and just $\sum_{k=1}^{\infty} n/p^k = n/(p-1)$ is just $1/(p-1)$ times the sum of base $p$ digits of $n$.

[sterile pumice]

Troposphere

[wooden glen]

So $\nu_p(n!) = \frac{n-(\text{base-$p$ digital sum of }n)}{p-1}$.

[sterile pumice]

Troposphere

[sacred junco]

Woah I never knew that last bit, holy crap that makes it super neat

[pale fjord]

could i do some doiuble induction?

[ornate scarab]

assume otherwise, then there exists a solution $(x_1,x_2,\cdots,x_n)$ with $x_i$ not all $0$.

consider the equation as a quadratic in terms of $x_1$, i.e.
$$x_1^2-(kx_2x_3\cdots x_n)x_1+(x_2^2+\cdots+x_n^2)=0,$$ so the discriminant is
$$\Delta=(kx_2\cdots x_n)^2-4(x_2^2+\cdots+x_n^2)=(kx_2\cdots x_n-2x_1)^2>0,$$

suppose WLOG that $x_1$ is nonzero and that it is positive, then by the quadratic formula, there exists a smaller positive root $x_1'$. on the other hand, if $x_1$ is negative, then there exists a larger negative root (repeat the argument as above, but with sign changes in the discriminant).

in either case, we produced a new solution $(x_1',x_2,\cdots,x_n)$ with a smaller absolute sum $$|x_1|'+|x_2|+\cdots+|x_n|<|x_1|+|x_2|+\cdots+|x_n|.$$

this contradicts our initial assumption that $x_1$ is a nonzero root.

[sterile pumice]

AeroBennu

[ornate scarab]

so much fun @pale fjord

[pale fjord]

hey i have another question: Find all natural number $(n,x)<20,$ such that $2^n -x=p.$ Where $p$ is a prime number

[sterile pumice]

erictheeonicpizhao

[pale fjord]

The idea is to take mod 4, right, but where to go from there..?

[wooden glen]

Is p fixed? Does "(n,x)<20" mean that the gcd of n and x is less than 20?

[pale fjord]

n and x have to be less than 20, and p can be any prime

[wooden glen]

Oh, then there's only 400 possibilities to check for primality -- quicker to script that stupidly than to attempt to be smart.

[pale fjord]

but we want an analytical solution... this is olympiad

[sacred junco]

<@&286206848099549185> help pls

[leaden swan]

@sacred junco we know
$x^3 \equiv -1 \mod p$
has almost 3 solutions

[sterile pumice]

DrunkenDrake

[leaden swan]

this reduces to the question of whether
$x^2-x+1=0 \mod p$ has solutions

[sterile pumice]

DrunkenDrake

[leaden swan]

You can complete the square and do quadratic residue trickery to get your answer

[sacred junco]

when do we use p is congruent to 1 mod 3

[leaden swan]

I guess to show existence of the said quadratic residue

If there's one quadratic residue, there's also another different one

[sacred junco]

probably to show one of these results

Also does this work

[frank night]

Hey

[sacred junco]

nice rengoku profile

[leaden swan]

Yea

[sand iris]

Have i proven this? The step where I raise each side to the 1/n felt weird to me im not sure i can do that

[coral trail]

how do i prove this?

[supple palm]

counter example would work fine

once you've found one, might want to consider what a^2 = b^2 mod m does imply

[coral trail]

i've been thinking about it
but i dont really know where to go with this

[wooden glen]

As Twiceshy said, just find a counterexample.

They're pretty easy to find, especially for small n.

[coral trail]

yeah, i'll do that

[wooden glen]

(There's no counterexample for n=2, though, but for n=3 it's hard not to find one).

[supple palm]

once you've found a counterexample, it might be interesting to note
|| the obvious counterexamples might be of the form a = -b mod m, as this represents when m|(a+b) but there may be others if m is non-prime. think abt why this might be possible||
|| e.g. 4^2 = 2^2 mod 12||

[elfin yacht]

anyone here did CEMC grade 11 contest ready to discusss?
ready to discuss all 25 questions for checking

[wanton viper]

Hallo!
I'm working on cryptography based on polynomials in finite fields and the word "Ideal" is quite common. I don't know what it is besides being a subgroup of the field that have a common aspect like the same zero point. Can someone give me a quick rundown what the most important properties are? I don't need any proofs, I want to generate a basic understanding for myself. Thanks!

[stiff rivet]

i will need more context, fields dont have ideals

ah well, the polynomial rings do

"most important properties" is a tall order though

would still need to know in what context they appear

[wanton viper]

how do i use the bot?

$F^n$

[sterile pumice]

[Hyp] Deutschland

[stiff rivet]

i mean you can just write it in a sensible way, its fine

[wanton viper]

ok

F is a finite field
T is a finite set of variables
y € F^n is the secret key
B ={q_j} is a subset of polynomials from F[T] with q_j(y) = 0
m € F is our secret message
we pick a p = sum(h_j * q_j) where h_j € F[T]
then our cypher is c = p + m
input: F, B, T, c
question: does c belong the the radical of the ideal generated by B

[stiff rivet]

🤔

some of this doesn't parse

you cannot evaluate a polynomial in $\mathbb F[T]$ at a point $y \in \mathbb F^n$ for $n > 1$

[sterile pumice]

Lochverstärker

[stiff rivet]

or what is T?

[wanton viper]

T is the set of variables we use in our polynomials

so if n = 2 we T = {a,b}

[stiff rivet]

ah, so like T_1, ..., T_n

[wanton viper]

yes

[stiff rivet]

ye ok, then it works

i mean this is some (classical) algebraic geometry except its gross because its not in a setting over an algebraically closed field

i dont think this can be explained if you have never seen what an ideal is

[wanton viper]

well, i completly understood how the cryptographic system works, i even coded a working en- and decryptor in java

its just for my understanding of the theory behind it

[stiff rivet]

does this system have a name

[wanton viper]

its very similar to Polly Cracker

but thats hard to google, there is some random "polly wants cracker" page that keeps poping up

i have a book about it (the crypto system)

[stiff rivet]

there is https://eprint.iacr.org/2011/289.pdf

based on the hardness of
computing remainders modulo an ideal in multivariate polynomial rings

this is easy enough to get

[wanton viper]

you mean to get the book or to understand? ^^'

[stiff rivet]

but your problem seems to be based on some algebraic geometry constructions

i mean to understand the quoted part

it also seems like a really weird question tbh

[wanton viper]

maybe i asked in a bad way? here is the part from the book

[stiff rivet]

but yeah, it seems the motivation behind this is algebraic geometry (which is hard) except its done over finite fields bcs computers

[stiff rivet]

oh ok, this is simpler

you will probably still have to look at an algebra book

you can think of this geometrically if you want

[wanton viper]

i passed a uni lecture about number theory, i think it was mentioned there, maybe the script has more information about ideals

[stiff rivet]

like the zero set of the polynomials is some geometric object

[wanton viper]

but the lecture had its focus more on finite fields and modulo p

[stiff rivet]

then taking the ideal means you can also add them and multiple them in whatever way

this doesnt change the zero set but gives you more functions

and then taking the radical does this again

so this is some geometric problem asking if c is on the variety defined by the polynomials

but i dont think this is helpful

this doesnt have anything to do with number theory a priori

but since you mentioned groups, ideals are like subgroups but for rings

they are also closed with respect to multiplication from the ring

and taking radicals of ideals is a geometric notion

algebraically its just a way to make the ideal bigger without changing its zero set

(this is probably all not very helpful)

[wanton viper]

it actually is

the idea behind the polly cracker is to create a polynomial that is very complicated but has one specific zero point

then add the secret message to it

when you evaulate c with y (the secret key which is the zero point) only the message remains

[stiff rivet]

ok so

when you have a polynomial f with f(y) = 0

then for all other polynomials g, you also have g(y)*f(y) = 0

and if you have g(y) = 0 and f(y) = 0, then also f(y) + g(y) = 0

so instead of considering the zeros of a set of polynomials, you can also consider the zero set of the ideal generated by those polynomials

this is more or less what you did here

we pick a p = sum(h_j * q_j) where h_j € F[T]

this p is a random element in the ideal generated by the q_j

it is still 0 where all the q_j are

this radical thing will enlarge the ideal even more without changing the zero set

but i think thats all i can say

i also have no idea why this is a hard problem

[wanton viper]

thank you!

the hardness of the problem comes from the idea that when you have a very polluted multidimensional polynomial it takes a lot of time the generate the secret key by calculating the zero point

like $|T| = 2^(500) and F_p with p=3000000019$

[sterile pumice]

[Hyp] Deutschland

[wanton viper]

damn bot

[stiff rivet]

its not the bots fault lmao

you have to enclose exponents in curly braces {}

[wanton viper]

oh xD

[stiff rivet]

this is standard latex

[wanton viper]

like $|T| = 2^{500} and F_{p} with p=3000000019$

[sterile pumice]

[Hyp] Deutschland

[stiff rivet]

it also doesnt matter lmao

[wanton viper]

why?

[stiff rivet]

i can read it fine

[wanton viper]

oh, i thought you meant the numbers i chose

^^'

[stiff rivet]

and i believe this is a hard problem but like

when you do encryption you want to be really sure

and this has a ton of structure that can (possibly) be exploited

still a cool use it seems

[wanton viper]

i can see a lot of potential for choosing wrong or way to easy polynomials

[stiff rivet]

yeah

if this only cares about zero sets, then

there are a lot of (rather recent ways) to make coefficients of polynomials smaller

without changing zero sets

not sure they work over finite fields though

[wanton viper]

ye, my prof. metioned something about this system not being secure anymore due to linear algebra attacks that are newer than the book (1988)

[stiff rivet]

oh yeah

there is also rather recent stuff on just straight up polynomial evaluation

very fast evolving field

[wanton viper]

i find stuff like this very interesting

[stiff rivet]

whats the book name if you dont mind telling?

[wanton viper]

Algebraic Aspects of Cryptography by Neal Koblitz

[stiff rivet]

interesting, didnt know koblitz does crypto

[wanton viper]

😅

anyway, thank you for your help!

[stiff rivet]

lmao, he created elliptic curve cryptography

ye sure

[gilded scroll]

<@&286206848099549185>

pls

[stiff rivet]

is this a test?

[gilded scroll]

@stiff rivet

help i got exam tommoow

i been asking this question and nobody fucking help me

fo 5 hous

@stiff rivet AE U GONNA HELP ME

[stiff rivet]

[gilded scroll]

@stiff rivet YES HELP

FFS

[stiff rivet]

you should read #❓how-to-get-help

[gilded scroll]

I WAITED

O SO LONG

<@&286206848099549185> Heplp

[stiff rivet]

what have you tried?

[gilded scroll]

nnothing

[stiff rivet]

stop pinging helpers, if you show zero effort

[gilded scroll]

i dont undestand the fucking question

i did ty

[stiff rivet]

what am i supposed to do?

[gilded scroll]

and go tt nothing

help e

duh

[stiff rivet]

i cant force you to study

[gilded scroll]

..

someone help me pls

and explain to me

[stiff rivet]

there is a lot to explain here

[gilded scroll]

..

[stiff rivet]

you have to study

[gilded scroll]

bro i havent lernt this

i know arithemtic

sequences

[stiff rivet]

i can see this

[gilded scroll]

and series

and geometic sequence and serie

i learnt that

what does that got to do with it

tell me

tell me

[stiff rivet]

you must read things on number theory

[gilded scroll]

ffs

u dont even know how to do it

your just a moderator

stop making it harder lol @stiff rivet

[stiff rivet]

i know how to do this

[gilded scroll]

u dont

u just a mo

d

same usualy mod

[stiff rivet]

and i am telling you that nobody can explain the entirety of modular arithmetic via discord

you need to use a different source

[gilded scroll]

i know what airthmetic is

I KNOW WHAT AIRTHMETIC IS

@stiff rivet

[stiff rivet]

ok nice

[gilded scroll]

.

SO WTF DO I NEED TO DO

[stiff rivet]

do arithmetic but modulo n

[gilded scroll]

WTF THAT

[stiff rivet]

its explained in the intro

essentially you do normal arithmetic and then reduce "modulo n"

[gilded scroll]

I DONT GET OT

IT

[stiff rivet]

this is more or less equivalent to finding the remainder when dividing by n

check the original example

[gilded scroll]

oh so

it says

[stiff rivet]

like 2*2 = 4 but if you divide that by 4 its 1 remainder 0

so the result is 0

[gilded scroll]

what does top got to with bottom

[stiff rivet]

or like 3+3=6 divided by 4 thats 1 remainder 2

so the result is 2

[gilded scroll]

i dont get the top

i dont get the graph

i get it

since the mod

[stiff rivet]

so you have stuff like $6 \equiv2 \pmod{4}$

[gilded scroll]

when its - or +

it will be the same remainder

YES I GET IT

[sterile pumice]

Lochverstärker

[gilded scroll]

6 divide by 4 = 2 remainder

and 2 divide by 4 is 2 remainder

i get it

okay i get it

i mean 4

now what ...

[stiff rivet]

now you do the same modulo 5

thats the exercise

[gilded scroll]

..

hoe

hpe

how

[stiff rivet]

what remainders occur on division by 5?

[gilded scroll]

oh i get it

so look

[stiff rivet]

you dont have to keep posting the image

[gilded scroll]

i dont get it

for reall

help me

[stiff rivet]

i am trying

[gilded scroll]

ok

[stiff rivet]

its the same computation as above except for 5 instead of 4

[gilded scroll]

k

[stiff rivet]

so if you get the thing above, you should be able to reproduce it

[gilded scroll]

can we do the left side first

explai it

[stiff rivet]

i am not doing this for you

you will have to do it yourself

[gilded scroll]

oh o

a = b (mod 4)?

[stiff rivet]

if you have a more concrete question, i can help you

or look at your solutions

[gilded scroll]

is it that

A= B (MOD 4)

[stiff rivet]

hm?

[gilded scroll]

it says

[stiff rivet]

are you sure you get how to read the tables above?

[gilded scroll]

there operation are detemriend through modulu 4

airthmetic

ya!

@stiff rivet is like basic multiplication table

with differet functions

[stiff rivet]

yes

so you write down the same table for 5

[gilded scroll]

wdym

write same table for 5

[stiff rivet]

well

first try to figure out why the table above only has the numbers 0 to 3

for arithmetic modulo 4

[gilded scroll]

@stiff rivet please help

[fiery iris]

do you understand what numbers fall in the set modulo n

[fiery iris]

that’s what he’s tryna get at

[fiery iris]

a = b mod c
means b is the remainder when you divide a by c. that’s a nicer way of thinking about it
alternatively
a-b will perfectly divide into c

[fiery iris]

so if take k = x modulo n
what is the set of possible values for x?

@gilded scroll

in case i’m not here when you’re back,
i’ve put the answer here
||{x E Z+: 0 <= x <= n-1} ||

do you see why ?

if yes, you should have absolutely no problem with your question

[wanton viper]

@stiff rivet i had my presentation today, thanks for all the help about ideals! The prof liked it when i made a sidenote to ideals

[stiff rivet]

oh cool

glad it went well

[sacred junco]

when I saw this I thought I was still in one of my language exchange servers and I was wondering why someone was talking about a presentation related to ideals in algebra in a German/English class

[wanton viper]

lel xD

[tender smelt]

Are there any interesting mathematical facts about 3, 5 or 7-smooth numbers?

[sacred junco]

bruh there's A CHANNEL NAMED AFTER A BOOK?

[sweet mist]

which channel is that

[formal minnow]

they’re probably making a terrible joke about this channel

[sacred junco]

these memes are so dumb ;-; I tried this for an hour and didn't get far. Mostly tried rewriting as quadratics in a or b and saving that the discriminant must be square for later, and then playing around with examining things mod 4 and mod 16 but nothing turned out

can one of them genius 9yo olympiad pros crack this

even did some case work mod 4 or 16 and it got a lil too messy but that could be it? idk

I'm terrible with judging red herrings when it comes to problem solving of human curated problems

[stiff rivet]

i think you need theory of quadratic forms

[sacred junco]

So like reformulating this to the problem of a^2 -kab + b^2 representing k implies k is square

[stiff rivet]

something like this

this is like the quadratic form (1, -k, 1)

you can compute a unique representative in its equivalence class

and then maybe you just see it?

or you need the class number

[sacred junco]

me wishing I had finished the 2nd half of hatcher number theory

[stiff rivet]

ye

chapter 5 should give you the tools to solve this

[sacred junco]

hmm lol a little motivation from a meme to keep reading huh

maybe I will

[stiff rivet]

what a weird image tho

why is there a random unrelated question on top

[sacred junco]

no clue LOL

I was scrolling r/wirklichgutefrage and found it

[stiff rivet]

[sacred junco]

Ugh the math is so pretty in that book I wanna finish it now

I get so happy whenever I see something in the wild where I can be like "hehe actually these are the only solutions cause of my magic infinitely repeating magic tree picture made from continued fraction dust"

🪄

[stiff rivet]

lol

i never see anything like this in the wild

[inner anchor]

thats like imo 1981 p6

the vieta jumping thing

[kindred junco]

this is one of the hardest questions ever

[stiff rivet]

its not that bad

but it requires some theory

i dont think you can solve this by just applying standard "elementary" toolset

[wise badge]

why is x^2 + pq *y^2 never equal to p when: -pq is not congruent to 1 mod 4 (where p and q are distinct primes, and x and y integers)?

[paper lion]

I'm trying to tackle this without any direct number-theoretic argument and it seems promising

I might be misremembering this, but we could set a=msin(x) and b=mcos(x) for some suitable choice of m. That way the numerator reduces to m^2, while the denominator gives us 1+m^2sin(x)cos(x). Restricting ourselves to those values of x for which m^2sin(x)cos(x) is an integer might end up reducing the fraction to a perfect square, although this is solely based on the heuristic that x=0 and x=π/2 work.

This also warrants justifying why m must be an integer in the first place

Maybe not as promising as I initially thought

[stiff rivet]

there is a generalization of this problem, replacing 2 by n

then you have to do some descent type argument, i.e. the vieta jumping that someone already mentioned

[ionic pier]

That's 'the famous question 6', a guy from my country got a special prize for proposing the solution with Vietta jumping

[trail oriole]

This is probably a stupid questions but.. I obviously know what primes are, and most, probably all, cryptographic protocols eg DH use groups of prime order.. but I still havent figured out why exactly those groups have to be (very large) primes.. does someone happen ot have a good explanation why primes matter so much especially in cryptography

[stiff rivet]

you dont need primes in diffie hellman, integers modulo a prime is just a good source of cyclic groups (which is what you really need)

they have to be large as to not make the problem easily solvable by brute force

a lot of number theoretic problems like discrete log (diffie hellman) are easier to solve on smooth numbers however (numbers having only small prime factors), so large primes play an implicit role

[haughty tundra]

this is the problem terence tao failed to answer at IMO 1988

[wise pulsar]

vieta jumping

there's a trick for questions like these

[verbal cedar]

when dealing with prime fields (p>2), can one use Fermat's little theorem to say that a^(p-2) is a general formula for the multiplicative inverse of any given nonzero element a?

[supple timber]

Yes

[atomic fractal]

how to prove that n^2 <= n^3 implies (n+1)^2 <= (n+1)^3 ?

[haughty tundra]

either induction or by expanding the terms and showing (n+1)^2 <= (n+1)^3

[atomic fractal]

i want to use induction

[atomic fractal]

with base case it's correct, but not sure what is the inductive step

[haughty tundra]

how far did you get?

[atomic fractal]

applying the transform n^2+2n+1 <= n^3 + 2n + 1 which is (n+1)^2 <= n^3 + 2n + 1

[haughty tundra]

using the assumption from the base case you can substitute n^2 for n^3 and show that the left side is still smaller than that

[atomic fractal]

yep

i got it

[atomic fractal]

thanks

[sacred junco]

I need help understanding why X and Y are defined in this particular way for this proof. The way n is defined as the product of ab seems very natural to me for example.

The book has the entire proof in it, if it helps.

[rancid sandal]

Difference theorem/formula is where X and Y come from, n = ab is really just the defining feature for n being a composite number

[olive rune]

$n^k \equiv 1 \text{ mod } k$

Trying to get solutions to this equation for a given $k$. It seems that the set of solutions n is linear (ie. take $k=2$, we get the set of solutions $n=1+3m$, where $m\in \mathbb{Z}$), but I don't know how to prove it

[sterile pumice]

amberhalo

[earnest raft]

My friend sent me this and I don't know how to solve

Assume A=R+R^2+R^3+…
Then AR=R^2+R^3+R^4+… and AN=NR+NR^2+NR^3+…
Given that N,R≠0 or 1

Prove that:

1. AR≠A
2. Write an expression for R in terms of A and N.

[sacred junco]

think subtraction

[earnest raft]

? I mean how…

[sacred junco]

you know, subtraction

[earnest raft]

ah, so AR-A=R

so then since R has a value AR≠A?

[sacred junco]

pretty much

but A - AR = R

[sacred junco]

Did you make any progress?

[olive rune]

no. still pretty lost. it looks very similar to fermat's little theorem, but there is a reduction of power

[sacred junco]

The name's Bjárke Erlandsson, the Viking from Thulthuree, and I have an Answer for thee! Consider the equation modulo three!

[sacred junco]

Did you notice that if n = 1 + kt, then the congruence is satisfied?

[olive rune]

kind of? I was seeing it followed the form n = 1 + cm, where c is a constant and m is an integer

[sacred junco]

Well, if n = 1 + kt, then n^k = (1 + kt)^n = 1 + km, with some appeal to the Binomial Theorem I think.

[olive rune]

im not sure i follow

[sacred junco]

Every term in the expansion of (1+kt)^n is multiple of k, except for 1^n.

For example, (1 + kt)^2 = 1 + 2kt + (kt)^2.

The name's Bjárke Erlandsson, the Viking from Thulthuree, and I have an Answer for thee! Consider the equation modulo three!

[olive rune]

k=3?, or do you mean something else. im not very comfortable with number theory so im a little lost

[sacred junco]

well then, what happens to the remainder after division by ten?

Oh Wutan do i have an answer for you, subtract this equation from itself considered modulo two !

[olive rune]

hmm

maybe this question is a little too advanced for me atm

[sacred junco]

Well, did you work out the case where k = 2?

Or k = 3?

[olive rune]

yeah, they follow the pattern you were describing

[sacred junco]

Okay, did you work out k = 4, because it's slightly different there.

Fear not, the answer is simple! You can solve it without getting a wrinkle!

[olive rune]

no, not yet

oh

thats interesting

you get two sol.?

[sacred junco]

Yeah

I think it should be that way for any even k.

Fear not, the answer is simple! You can solve it without getting a wrinkle!

But I don't know if that's all the solutions or only some.

[olive rune]

sorry just understanding this now

thats clever

[olive rune]

how did you go about it?

[sacred junco]

To get the solution without any intrution, i considered a dirichlet convolution

[vernal ibex]

https://media.discordapp.net/attachments/328208536029102081/953252325433155594/20220315_165407.jpg

https://media.discordapp.net/attachments/328208536029102081/953252325781299200/20220315_165156.jpg

Why Must d or p,q and d be divisible by 3?

[sacred junco]

Suppose d=1 mod 3. Then if p = 1 mod 3, this leads to r being a multiple of 3, a contradiction as it is prime. Similarly p = 2 mod 3 won't work as then q will become a multiple of 3. Similarly argue the other case of d = 2 mod 3.

[vernal ibex]

Hmmm I See.

Can I DM Other doubts?

[wanton torrent]

Hey guys

So I have a system of equations

$x = \frac{ay - c}{b}$ and $y = \frac{c+bx}{a}$ where $x,y,a,b,c \in Z_n$ I don't understand how can I solve such

[sterile pumice]

mns

[wanton torrent]

when does it have a solution?

[wanton lodge]

@wanton torrent could you send the original question/problem?

[wanton torrent]

I must find all conjugacy classes for the heisenberg group over Zn

[wanton torrent]

.

[mental quarry]

bx = ay - c
ay - bx = c

Isn't this a linear diophantine equation?

This is all I can come up with @wanton torrent

[wanton torrent]

Yeah I got that as well

[fossil cape]

Looking at quadratic residue over a finite field, I'm given the following equation x^2 + 1 . Can I use the quadratic formula to figure out the solutions?

maybe $y^2 = x^2 + 1 mod p$

[sterile pumice]

hello123456789

[fossil cape]

then to solve for y, I can maybe do $y^2 - x^2 - 1=0$ and solve for y

[sterile pumice]

hello123456789

[fossil cape]

If we say let t = x^2 -1 , we can do y^2 - t^2 =0 and the solutions for y is \pm sqrt(t)

I'm not sure where to go after that because I do not know a way to see if x^2 -1 is a square

[leaden swan]

There's a much easier way of doing this

(y-x)(y+x)=1 mod p

Ok that doesn't sork

[fossil cape]

y-x and y+x are inverses or I think they are both 1 in your equation

[leaden swan]

y-x = a then y+x=a^-1 then y=(a+a^-1)/2 and x=-(a-a^-1)/2

So all solutions are of that form

((x-x')/2,(x+x')/2) where x' is inverse of x

[fossil cape]

Unless I'm reading it wrong, do the solutions always exist?

[leaden swan]

If the solution exists,it has to be of that form

The other direction is you show all pairs of this form satisfy the equation

[fossil cape]

How do I know if they exist?

[leaden swan]

Pick a random x and generate a pair

If a is an arbitrary residue(non-zero)

((a-a')/2,(a+a')/2) is a solution by substituting

The only case where this is not possible is p=1 but that's not prime

[fossil cape]

okay thanks, i think I am missing something since I start with x^2 + 1 and by your messages it seems that it is always a residue

[fossil cape]

Hmm but how do I find a?

[leaden swan]

Any non-zero a will work

[fossil cape]

If I already have x ?

[leaden swan]

x will be (a-a')/2

Find a from there

Yea that will be a quadratic

[fossil cape]

what do you mean?

[leaden swan]

$x=\frac{a-a^{-1}}{2} \mod p $

$\implies 2ax=a^2-1 \mod p$

[sterile pumice]

Drink Drake

[leaden swan]

$\implies a^2-2ax-1=0 \mod p$

[sterile pumice]

Drink Drake

[leaden swan]

Which is a quadratic in a

Actually There is an infinitely better way of doing this

[fossil cape]

Oh whats that?

[leaden swan]

y will just be square root (x^2+1) mod p

If square root is too expensive you can do the quadratic approach

I am not sure how good the square root approach is actually

Nvm,Tonelli shanks seems like pain compared to the quadratic approach

[fossil cape]

hmm with your previous approach, could we take the discriminant to find if there are solutions?

a^2 - 2ax -1 = 0

[leaden swan]

Yea sure

But actually I think this also devolves into the square root problem

[fossil cape]

If done right, I would get 4(x^2 +1 ) , so I guess discriminant is no help here?

[leaden swan]

Yea

[fossil cape]

Its strange, isn't there some way to say that numbers of the form x^2 + 1 in a field are all residue for example?

We can say it about x^2 by definition

[leaden swan]

It's funny how we literally came back to the question of checking if x^2+1 is a quadratic residue here

https://math.stackexchange.com/questions/398200/the-number-of-solutions-of-ax2by2-equiv-1-pmodp-is-p-left-frac-abp
This might be useful

[fossil cape]

will check it out, thanks!

[vernal ibex]

Why Mod 4 and how leads to the solution of this problem?

[leaden swan]

You gotta use the fact it's odd smh

Taking mod 4 is the first thing you try

[sterile pumice]

@inner crest

[noble tiger]

because mod 4 all perfect squares are congruent to 1 or 0. This means that for any odd x,y,z x^2+y^2+z^2=3 mod 4

[sacred junco]

can someone explain the point of diffie hellman cryptography

at which point did Alice send Bob a secret message

[torn escarp]

they haven't yet, all they've done is come up with a shared secret number that they can use as an encryption key so they can start sending messages to each other

[sacred junco]

how is 18 secret though? When Bob raises g^a to g^ab wouldn't a third party know that number

[torn escarp]

no because the only thing that gets sent in public is g, g^a and g^b not g^(ab) or a or b

try computing a knowing only g, g^a and p

[sacred junco]

oh right mb

[torn escarp]

it becomes pretty much just brute force trial and error of looking at g, g^2, g^3, ... until eventually you find g^a to determine a

yeah

it's pretty confusing haha

[sacred junco]

I'm assuming they somehow use this number 18 to get the plaintext from the ciphertext

And the third party is trying to get a and b so they can compute g^ab

[torn escarp]

yeah the shared secret can be used for a symmetric key encryption for encrypting plain text

also they only need to get either a or b, once they have one, it's enough to make g^(ab), so they can target whichever is weaker if one stands out

[sacred junco]

That's clever

It's also interesting how in RSA undoing exponentiation works differently

In diffie hellman it's the discrete log. In RSA it's raising to the inverse of the exponent in mod phi(n)

[torn escarp]

yeah they're really getting their money's worth out of the modular arithmetic lol

[sacred junco]

@torn escarp bruh what do they mean by message

i thought DH was only for agreeing on keys

i guess I haven't thought about what they do with that key

is it asking me to calculate g^a?

[sacred junco]

<@&286206848099549185>

[sacred junco]

<@&286206848099549185> anyone there

if you know | xy| = |a|, can you say |y| = |a/x|?

a is known to be positive

[leaden swan]

Yea

[leaden swan]

First time the message is g where you consider Beth sends g^b mod p and Alice sends g^a mod p

After that,when Beth sends it,it is g^b mod p

The thing with diffe Helleman is discrete log problem is conventional very difficult to solve

Ofc,There are ways to break the traditional diffe-hellman under specific circumstances

The secrets are a and b

They are asking you to calculate g^(ab) in the first Casey

[sacred junco]

thanks

I was confused cause they said secret message and not secret key