elementary-number-theory

[prime gust]

any idea how to solve x^4+x^3+x^2+x^1+1=y^2? for naturals numbers?

i managed to show that if a solution exist then x=8m or 8m+3 or 8m+7 for some integer m

and i substituted m=0 for all cases and found that x=3 y=11 is a solution in naturals (not including x=0 y=1 since 0 is not included in the naturals)
and now for m>=1 i need to show whether or not there is a solution. no idea how to

[fleet bone]

try to bound LHS between two consequtive perfect squares

[prime gust]

how can i do that?

i managed to show that y is odd so let y=2k+1 and substitute for the case x=8m+3 and you can simplify and get k(k+1)=(2m+1)(2(256m^3+288m^2+112m+14)+2)

and in the book i am reading they concluded that since k(k+1) is a product of 2 consecutive terms and since the LHS (2m+1)(2(256m^3+288m^2+112m+14)+2) is a product of an odd number 2m+1 and an even number 2(256m^3+288m^2+112m+14)+2
then 2(256m^3+288m^2+112m+14)=2m

which is logical to think that way

and if that is true then there is certainly no solution for x=8m+3 for m>=1 and for the cases x=8m and x=8m+7 the proof is similar

but the only thing that i dont understand is why they concluded that it must be equal to 2m.

[urban dust]

which book?

[prime gust]

Methods of Solving Number Theory Problems by Ellina Grigorieva

[fleet bone]

for example

Try to show it's between ( x^2+x) ^2and (x^2+x+1)^2

except certain finite values of x

It might not be between those I am just trying to give u a hint

,w (2x^2+x+1)^2>=4(x^4+x^3+x^2+x+1)>=(2x^2+x)^2

[sterile pumice]

Results provided by WolframAlpha

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

Requested by theguy4410

[fleet bone]

There u have it

[prime gust]

and then i just need to check for the cases x=3,2,1

[fleet bone]

ya

[prime gust]

okay thanks, anyway what about what I wrote? do you think what they did is valid?

[urban dust]

Umm, doesn't Wolfram say x>=3? How does that help?

[fleet bone]

U generally wanna guess these polynomials when u dont have wolfram

It's a common strategy

When leading coefficient is a perfect square

[urban dust]

I didn't understand the argument from the book either, I suggest emailing Ellina Grigorieva (she is a prof so can be located easily) 😛

[fleet bone]

this is given in ivan niven

with my solution

though its written as a theorom

[urban dust]

I mean isn't x>=3 infinite so how did it help reduce the search space? Unless I can't read :d

[prime gust]

wait 2x^2+x+1)^2>=4(x^4+x^3+x^2+x+1)>=(2x^2+x)^2 just talks about 4 times that is between 2 consecutives squares but that doesnt say on our original number

[fleet bone]

A perfect square doesn't exist between consequtive squares

Or perhaps I should change >= with >

,w (2x^2+x+1)^2>4(x^4+x^3+x^2+x+1)>(2x^2+x)^2

[sterile pumice]

Results provided by WolframAlpha

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

Requested by theguy4410

[fleet bone]

and equality cases

Though when solving without calculator u will find equality cases when solving ineq anyway

[fleet bone]

x^4+x^3+x^2+x+1 is pef sq is <=> 4(x^4+...+1) is perfect sq

[prime gust]

yeah just realized that lol

thanks

[urban dust]

oh nvm, I get it now. Cool technique. 👍

[primal pewter]

I just wanted an integer with a^2=1 (mod p); so I chose -1, and I replaced it by -1+7 for no reason

[robust warren]

Is anyone awake and in the mood for quadratic residues ?

Basically trying to show that if a is a quadratic residue mod p where p is an odd prime the its inverse, b is also a quadratic residue

[primal pewter]

just use (a/p)(b/p)=(ab/p)

or you can just say that there is some integer k with k^2=a (mod p)
then (k^-1)^2=a^-1 (mod p)

[robust warren]

I wouldn’t be able to use (a/p)(b/p) because that assumes b is a QR which is what I’m trying to prove

[robust warren]

For the second suggestion, have you just taken the inverse of both sides and then said that (k^2)^-1 = (k^-1)^2?

I didn’t know you could just take the inverse of both sides tbh 🙃

[west glade]

basically normal exponent laws

and well if both sides are equal, then also their inverses are equal (as long as they exist obviously)

[robust warren]

You mean their congruences

So like if a is congruent to b mod p and a has an inverse then is it necessary that b has an inverse ?

If so, are their inverses also congruent mod p

Oh right because it’s just about principle remainders isn’t it technically

a and b leave the same principle remainder on division by p so if a has an inverse then b must have an inverse and therefore their inverses must be congruent modulo p…

[primal pewter]

no, it doesn't
you know that (a/p)=1, and since ab=1 (mod p), you have (ab/p)=1; the equality implies (b/p)=1

[robust warren]

Hmm

What about the statement ab=1(mod p) implies that ab is a QR mod p?

[primal pewter]

1 is a QR mod p, right?

[robust warren]

Yes

[primal pewter]

well, then ab is also QR, by definition

(-1)^2 = ab (mod p)

[robust warren]

Oh right of course

Yea that actually seems like much easier way of doing it

That’s all good, thank you

[robust warren]

In terms of this statement though

This is just curiosity

How would you go about proving that if a=b (mod p) and a has an inverse

[primal pewter]

a and b are inverses to each other

[robust warren]

Then b must have an inverse

Here, b is nOT the inverse of a

It’s just something a is congruent to

[primal pewter]

if a has an inverse, call it c
you have ac=1 (mod p), but since a=b (mod p), it follows that bc=1 (mod p), so c is also an inverse for b

[robust warren]

Ahhh

Their inverses are in fact, the same

[primal pewter]

yes

when working modulo something, congruent elements are basically "equal" elements

[robust warren]

Got youuuu

That makes sense

Thank you very much

[robust warren]

I have a question on cryptography but we studied it as an application of congruences etc so it’s basically number theory

My scribbles are just me trying to make sense of the problem

For part a I’m just lost like

How would you decrypt that cuz it may be reduced mod p

Do I just subtract y and then multiply with the inverse of x

And then mod it by p

[normal heart]

yes, and reduce whatever you get to an integer between 0 and p-1. This is indeed the message M since p is a prime greater than M

[robust warren]

And this is clearly a symmetric cipher because they use the same keys to encrypt and decrypt

[normal heart]

idk what a symmetric or asymmetric cipher is since I don't know cryptography lol

[robust warren]

Don’t worry about that, I’m sure about that bit

Do you understand part c?

Cuz I’m not even sure what it’s asking tbh 😭

[normal heart]

I could vaguely guess what it means. I suppose Eve is given a message M_1 and the corresponding c_1, and also message M_2 and the corresponding c_2, and you are asked to show Eve could find x and y mod p

[robust warren]

I suppose that looks to be a simultaneous linear congruence if I’m not wrong

[normal heart]

actually i'm not sure if that's what the question is asking, I think someone with more knowledge in cryptography could answer this better lmao

[normal heart]

yeah i agree

[robust warren]

Oh okay, thank you anyway :’)

I’ll wait to see if a cryptography expert answers

[robust warren]

Meanwhile I’ll try to solve it like that

[robust warren]

Suppose this is a simultaneous linear congruence

Is this fair to say in that case ?

[normal heart]

Should go into more detail in the last sentence

write it out more explicitly
since at some point you need to use M_1 =/= M_2 mod p

[robust warren]

Hmm let me try

Is that pretty much what’s happening

[normal heart]

not sure how much you need to write out, but I'd write 'since p is a prime, this implies gcd(p,M_1-M_2)=1, so inverse exists'

i'd also put a 'mod p' at the end there

[robust warren]

I’ll add like references to proofs etc throughout

[robust warren]

Yea I was planning on that in the final write up

Right now I’m just trying to figure out what even is happening

[normal heart]

i think it's fine at large

provided that's indeed what the question is asking, lol

[robust warren]

Oof yea

But I think it is tbh

[scenic abyss]

How can I prove that any natural number greater than 1 is the sucessor of another natural number?

[tight eagle]

Need help determining if this number is constructible or not

this is what I have

[weary ivy]

yeah looks correct

[tight eagle]

If I've calculated the 5th roots of unity how can I draw using a straightedge and compass a pentagon using them

[wooden glen]

Your calculation should have ended with some expressions for each real/imaginary part that involve rational numbers and square root signs.
Do you know how to implement arithmetic and extract square roots using compass and straightedge?

[weary ivy]

btw there's a construction for a regular pentagon with straightedge and compass

[tight eagle]

No thats what im confused about

[tight eagle]

Yea but I need to do it specifically from my result from calculating the 5th roots of unity

[grand umbra]

Let m, n, p, q be integers satisfying the following condition: m + n + p + q | mnp + npq + pqm + qmn
Prove that m + n + p + q is a composite number

[primal pewter]

@grand umbra you probably mean positive integers; otherwise one can make m+n+p+q to be 1

[grand umbra]

ah yea

positive integers, i mean

[primal pewter]

here is a solution (I will jus t use a,b,c,d instead of m,n,p,q)

assume a+b+c+d is prime;
write abc+abd+acd+abc=ab(a+b+c+d)+(cd-ab)(a+b)
since a+b+c+d divides this, it follows that a+b+c+d | (cd-ab)(a+b)

since a+b+c+d is prime it follows that a+b+c+d | cd-ab or a+b+c+d | a+b, but the second case is impossible because a+b+c+d>a+b

so we have a+b+c+d | cd-ab

similarly, we get a+b+c+d | ad-bc

add them, and you get a+b+c+d | (a+c)(d-b)

and a+b+c+d being prime implies a+b+c+d | a+c or a+b+c+d | d-b
however, both are impossible because a+b+c+d is greater than the number on the right

[grand umbra]

damn

one of the most elegant solution ive ever seen to a problem lol

ty

[primal pewter]

I've got the idea from a problem that I saw some time ago: if a,b,c,d are positive integers with ab=cd, then a+b+c+d is composite.

[wooden glen]

Addition and subtraction of line segments is easy. Multiplication and division you can do by constructing similar triangles (or in many special cases simpler than that). For square roots, see e.g https://math.stackexchange.com/questions/705/compass-and-straightedge-construction-of-the-square-root-of-a-given-line

[keen inlet]

So I was trying to prove if $a=qb+r$ then $(a,b)=(b,r)$ I did the following:

$(a,b)=ax+by=(qb+r)x+by=qbx+rx+by=b(qx+y)+rx.$

Would this be sufficient to prove the statement?

[sterile pumice]

granted9894

[fleet bone]

Depends on what u precisely mean by " calculated" .

It can mean many things u wrote them on a piece of paper

u have plotted it

however none of these things are mathematically defined in the first place

Unless u have the lengths of their real and imaginary parts in a line segment it won't help

because straightedge doesn't have measurements

and in compass I will also assume that

[pastel vigil]

No. You're first of all assuming without reference that the gcd is a linear combination (of course it is true but do refer to the theorem you're using).

Moreover, you only prove that (a,b) is a linear combination of b and r, but that doesn't prove it is the gcd of b and r. It does prove it is a multiple of (b,r).

[fleet bone]

Also the proof of linear combination comes from division algorithm which already uses this result

[keen inlet]

Sorry let me explain, in my book we do not use a theorem. This is because we are working with (a,b) as the ideal generated by a and b in Z so by definition it is a linear combination. So I was thinking if I did this then there is some kind of equality between the elements of the ideals

[surreal tangle]

You just need to be able to construct angles of 72° right?

And then just make 5 line segments originating from the same point with an angle of 72° b/w them and join the ends

[pastel vigil]

Ah, in terms of ideals, (a,b) is not a linear combination, but the set of all linear combinations. So now you are confusing a set with a generic element it contains. But still your argument would only show that (a,b) is a subideal of (b,r).

[thick panther]

hey; for the first part of the question, im not quite sure how to finish off my proof
this is what i did:
suppose that a is a QR
then by Euler's criterion we have (a/p) = a^[(p-1)/2 ] = 1 mod p since (a/p) is a QR
thus a is not a primitive root since we require a^(p-1) = 1
other direction:
suppose a is now an NR (i assume by the wording of the question that we dont care about 0)
then (a/p) = -1 = a^(p-1)/2
and so a^(p-1) = 1 mod p

this is most of the proof done, but one thing i havent done is justify that in fact we dont have a^k = 1 for k < p-1 and im not really sure how to go about it either, could i get a pointer in the right direction?

[primal pewter]

@thick panther the first part is correct (you should just point out at the end that we require p-1 to be the smallest number with a^(p-1)=1)
to continue the second part, do this:
remember that p = 2^(2^n) + 1
so a^((p-1)/2)=-1 becomes a^(2^(2^n - 1))=-1
now, say k=ord_p(a); you have k | p-1 (and substitute p)
prove that k cannot divide 2^(2^n - 1), and combine the last two things

[keen inlet]

Yes yes, sorry again I had just woken and wasn't being super clear and it appears I wrote something last night I didn't mean to lol. I see now so I should just add $r=a-qb$ then I'll have for any element of $(a,b)$ say $ax+by=qbx+rx+by=b(qx+y)+rx$ so $(a,b)\subseteq (b,r).$ Then take any element of $(b,r)$ say $bm+rn$ then $bm+rn=bm+(a-qb)n=bm+an-nqb=an+b(m-nq)$ thus $(b,r)\subseteq (a,b)$

[sterile pumice]

granted9894

[thick panther]

sorry, i understand what your hint is getting at but ive been staring at it and im not sure how im supposed to exactly prove that k cannot divide 2^(2^n-1) [or 2^2^n for that matter]

[primal pewter]

if k divides 2^(2^n - 1), then 2^(2^n - 1) = k*m, for some integer m
from a^k = 1, you would get a^(k*m)=1, contradicting the fact that a^(k*m)=a^(2^(2^n - 1))=-1

[thick panther]

ohhhh

i see i see

thank you 🫡

[fleet bone]

indeed but OP said to use the result of calculation

[fleet bone]

.

[thick panther]

hello hello, i come with another question; but rather to check that i understood everything:
(a) was fine and i dont think it was relevant to other parts of the question
(b) if we have odd + even = even (which is false) thus they must have the same parity if they're both even then the whole thing will be divisible by 16 (since c would have to be even also) and we return to where we were. if we keep going, if it is always even and even, then by well ordering principle theres no solution.
if it is odd + even, then a solution didnt exist in the first place
thus we must end up with odd and even and if our original equation has a solution then there must be a solution for which they are both odd
(c) note that if gcd(a,b) = 1 then gcd(a,b,c) = 1
suppose that p|a and p|b for some prime p
then p|c also meaning that we can cancel a factor of p^4 (since p^2 has to divide c)
we keep repeating this until we have some p | a but not p | b

what i need help with:
firstly, i would like someone to confirm whether i missed something within my solution making it incorrect
secodnly, as you can see, this is very unrigorous 💀 thus, if i could have some help formalizing it i would be very grateful; especially the "if we keep going", i'm not really sure what else to write (unless this is good enough?)

[keen inlet]

Am I missing something here or is this just a simple application of the fact that if $d$ is a gcd then $(d)=(n_{1},n_{2},\dots, n_{s})$?

[sterile pumice]

granted9894

[wooden glen]

If you have enough ring theory available for that argument to make sense, then yes.
(But of course you might have to prove that the positive generator of the ideal also has the property of being "greatest common divisor").

(Though perhaps, since you get to pick your definition yourself, you can just make that property your definition!)

[keen inlet]

This is Ireland and Rosen so they prove that first there is always a d such that (a,b)=(d) and then that this d is exactly a gcd (they use the term a as they don't always require d to be positive)

[thick panther]

could i get a hint for 5.3 please?

[primal pewter]

@thick panther
prove that 2x is invertible mod p
deduce that there is a k such that the congruence in 5.2 holds
conclude

[vestal wagon]

So this is interesting

While helping someone in this server I noticed that 3! * 4! happens to be equal to (3*4)^2

So I graphed x!y!=(xy)^2

Funny looking graph

If you zoom out and do a regression is roughly follows the curve y=-x

[wooden glen]

The gaps in the cuves are due to software limitations; actually there should be solution points close to any point where one of the coordinates is a (not too small) negative integer, due to the poles of the gamma function.

[sleek cove]

what?

[light flicker]

yep ur a number theorist

[sleek cove]

?

and u are?

stick to playing with ellipticals

[formal tiger]

GG I have just finished my number theory final exam!

[keen pagoda]

for two primes p and q, can p-1 divide pq - 1

oh and p not equal to 2

[patent acorn]

p=7, q=19 works

[primal pewter]

@keen pagoda of course; pick p=3 and q=5

[keen pagoda]

h,h,,umhmuh

I actually found more example out at the same time

sad

[patent acorn]

mod p-1, pq-1 = q-1, so the question is just "can p-1 divide q-1 for primes p,q"

[keen pagoda]

oh damn

[primal pewter]

and the answer is yes by Dirichlet's theorem: there are infinitely many primes of the form an+b, where a and b are coprime integers

[keen pagoda]

that's cool

need to learn more number theory

it'd be so nice if it couldn't for specific reasons

[white lion]

maybe explore it with more restrictions

[lunar creek]

k and C are constants which are natural numbers (k>C)
how can i find a solution for the equation below so that y + x is minimized (also y and x have to be whole numbers)
yk+y+x=C

like finding whole number solutions
not the hardest of problems (given some k and some C) because you can just say y=0 and x=C
but that wouldn't be the smallest value for y+x

[marsh oyster]

Looks like you want to compute the quotient y and remainder x when dividing C by (k+1), so the answer is just "perform a division algorithm"
Your request to minimize x+y is the same as maximizing y since the coefficient of y is bigger than the coefficient of x, and taking the biggest y you can is exactly what you do when performing divison

[lunar creek]

is there no second equation I can use to just make a system of equations?
the division thing seems to work tho

[marsh oyster]

Don't think a system of equations would make sense

[lunar creek]

I see

[marsh oyster]

Though I realized you said k>C, if that's the case and you're looking for nonnegative solutions then you'd just have y=0 and x=C

[ripe plaza]

Given the following:
How does q boil down to that?

[white lion]

Im trying to find a nice proof to prove that fact that p choose k for $1 \leq k \leq p -1$ is divisible by p where p is prime, this is my proof clearly p choose k must be an integer call it $a$ so we have that $\frac{p!}{k!(p - k)!} \equiv a \pmod p$ therefore $\frac{p!}{k!} \equiv a(p - k)!$ clearly the left-side is 0 hence we get that $a(p - k)! \equiv 0 \pmod p$ so $a$ or $(p - k)!$ is 0 if $(p - k )! \equiv 0$ we get a contradiction hence $a \equiv 0$ , as needed.

[sterile pumice]

jayz

[edgy sapphire]

Yep this is fine

[prime gust]

let {} denote the fractional part of a number x then {x} is defined as follows: {x}=x-floor(x).
prove that if gcd(a,n)=1 then {a/n} , {2a/n} , .... {(n-1)a/n} is a permutation of 1/n , 2/n , ... (n-1)/n

[still flare]

I assume you want a hint or some help with this and you're not just sharing this for the fun of it...

Hint: the residue class of a mod n is determined by {a/n} uniquely.

[prime gust]

yeah xd, i did figure it has this relation but i just couldnt prove why tho, I did manage to prove that all the numbers {a/n} , {2a/n} , .... {(n-1)a/n} are distinct since otherwise we would have a contradiction with the fact that gcd(a,n)=1 but i did not achieve any further progress 😦

[still flare]

Hint: division algorithm.

[prime gust]

Yep, i am an ape

Since all of them are distinct then there are n-1 different numbers

All of the number satisfying aj<n for 1<=j<=n-1 are equivalent to j numbers {a/n} ... {ja/n} from 1/n ... (n-1)/n

And if aj>n then by divison algorithm aj=nk+r for 0<r<n-1 r!=0 since if r=0 then aj=nk meaning n must divide j since a is relatively prime to n which is a contradiction since n is bigger than j

And so 0<r<n-1

The fractional part of <aj/n=(nk+r)/n=k+r/n is r/n and they complete the permutation since the fractional parts are distinct and there are n-1 of them

I am often such a monkey

[rose birch]

is it true that gcd(2^p -1 , 2^q -1) = 1 for two distict primes p,q?

[coral venture]

Yes

gcd(a^n-1,a^m-1)=a^{gcd(n,m)}-1

So gcd(2^p-1,2^q-1)=2^1-1=1

[rose birch]

where does this come from?

i dont think I need this after all actually but still interesting result

[coral venture]

Euclidean algorithm

you can also use bezouts identity

[sterile pumice]

The

[rose birch]

I think my argument here should be good

I wanted this as I was taking N to be (2^qi - 1) but i think I can just take 2^Q -1

[open mist]

These are serious math channels
Memes, jokes and other nonserious posts don't belong here. They may belong in #chill but I'm not knowledgeable about that

[jolly aurora]

How would i solve
27=10^x mod(29)

[wooden glen]

Trial and error. If you notice any shortcuts along the way, grab them.

However, such "discrete logarithm" problems are notoriously difficult at scale, and there's no known general procedure that's significantly better than trial and error.

[jolly aurora]

ahh ok thanks

[burnt aspen]

I have a problem with a task to find all positive integers n such that an equation x+y+z+t=n*sqrt(xyzt) has a solution in positive integers. I figured out that n can be equal to 1, 2 or 4 and then the solutions are x=y=z=t=4 or 2 or 1 respectively. I assume that there are no other such n, but I don't really know how to proceed. If n was a composite number such that this equation has a solution then divisors of n would also satisfy this condition because we could multiply both side by other divisors and get a new solution for different n. So to show that there is no composite n other than a power of 2 would suffice to show that there is no prime number > 2 that would satisfy this condition. But I don't know how to do that and I don't know what to do with other powers of 2

[foggy shell]

Can't you get an infinite amount of solutions form just one?

If we suppose that the variable x,y,z,t and n constitute an arbitrary solution to
$$ x+y+z+t=n\sqrt{xyzt}$$
Then if we can construct another solution with any integer $a$ where $x_1=ax,y_1=ay,z_1=az, and t_1=at$. Plugging this in gives us
$$x_1+y_1+z_1+t_1=n\cdot\sqrt{x_1y_1z_1t_1}$$
$$a(x+y+z+t)=n\cdot a^2 \sqrt{xyzt}$$
$$x+y+z+t=na\sqrt{xyzt}$$
So $n_1=an$. So I guess not, because a would have to be 1

[sterile pumice]

catman

[burnt aspen]

Yeah, this is not homogenous so you can't get new solutions like this. But this shows how you get from an existence of a solution for n composite to an existence of a solution for divisors of n, as I wrote before

[charred roost]

Have you tried reducing it modulo 2? I don't know if it helps, you might have to do a cumbersome case analysis on the parity, but it might be worth trying

[white lion]

there would be 4^4 cases... cumbersome is an understatement

[sterile pumice]

catman

[white lion]

try when y = x and t = z

see what you get

[foggy shell]

if they are all the same then you just have the set of numbers where $a^2|4a$

[sterile pumice]

catman

[charred roost]

I think there are some shortcuts - for example, the right side is even if any of x,y,z,t are even, but the LHS is even if 0, 2 or 4 of x,y,z,t are even

[foggy shell]

if 2 sets are the same then you have
$$ab|2(a+b)$$
and from this either $ab|2$ or $ab|a+b$

[sterile pumice]

catman

[burnt aspen]

Yeah, I've tried but it doesn't lead to anything interesting tbh. I also checked it modulo 4

By going modulo 4 we have that we need to have that xyzt=0 or xyzt=1, so either at least one of them is 0 mod 4 or two or four of them are 2 mod 4 or there is an even number numbers x, y, z, t such that they are 3 mod 4.

In case one of them is 0 mod 4 (bwoc x=0 mod 4) then y+z+t must be equal to 0 mod 4

So that means that BWOC either y = 0 mod 4 and z=-t mod 4 or y=z=t=2 mod 4

And in the case that $xyzt=1 \mod 4$ then from the reduction that was earlier we can assume that $n$ is an odd prime so we have that RHS$=1$ or $3$ and that means that in case that RHS $=1$ mod 4 we have $x+y+z+t=1$ mod 4 and we get contradiction because $x,y,z,t$ are 1 or 3 mod 4, so we don't have any solution and the case that RHS$=3$ mod 4 is similar

[sterile pumice]

Zuzia

[burnt aspen]

So finally we get that at least two of $x,y,z,t$ are even

[sterile pumice]

Zuzia

[charred roost]

Another approach to showing there are no more solutions is looking at the asymptotic size of each side. For example, when x,y,z,t are all >4, there are no solutions, because the (absolute value of the) LHS is always smaller. And equivalently when 3 of x,y,z,t are bigger than 16. It restricts the possible values somewhat, but maybe not fully

[burnt aspen]

That's a good point, but I don't know if it helps. For n=2 x=2, y=6, z=1225, t=56307 is a solution (I have run computer experiment randomly choosing numbers and checking if the ratio (x+y+z+t)/sqrt(xyzt) is an integer to search for new solutions and this was the only answer that I got after hundreds of milions runs.) and this asymptotic approach wouldn't catch it

Maybe I should add that in our classes we recently had Lagrange's four squares theorem, Jacobi symbols and order of elements. This problem might be linked to one of these but doesn't need to

As I said earlier proving that for any odd prime p there is no solution would almost solve the problem. So checking this equation with n=p, assuming that there is a solution and by using Legendre symbol we get that
$$ x+y+z+t \equiv 0 \text{ mod } p$$
And
$$\left(\frac{xyzt}{p}\right) =1$$
But I can't see if it helps

[sterile pumice]

Zuzia

[burnt aspen]

For n=3 this equation is also solvable (x=y=1 and z=t=2), so x+y+z+t=6=3*sqrt(xyzt) and it is the only solution modulo permutation for 2 pairs of equal numbers

[foggy shell]

Why are congruences used here?

[wintry locust]

if I have 3 equations:

1. x^a = 99 (mod 101)
2. x^(ab) = 48 (mod 101)
3. x^b = 18 (mod 101)
   can I evaluate x?

a and b are unknown

[wooden glen]

That's basically the Diffie-Hellman problem, isn't it?

No, not quite, usually x would be known but x^(ab) wouldn't.

You know 18^a== 48 (mod 101) and 99^b == 48 (mod 101), so you can brute-force search for a and b.

[wintry locust]

the question is asking to find x

the 3 equations were all i could think of given the restricted information

[wooden glen]

Once you know either a or b, you can brute-force a solution to x^a == 99.

What is the original problem?

[wintry locust]

exchange a key x using the Diffie-Hellman Key Exchange scheme. The messages communicated in the three step process are 99, 48 and 18, respectively. Determine x given p = 101

[wooden glen]

What, are they actually putting x^(ab) in a message? They shouldn't do that.

Oh, I see, you're taking powers the opposite way of normal Diffie-Hellman.

... perhaps.

Perhaps you had better show the definition of "the messages communicated" in your particular variant of the protocol.

[wintry locust]

reading back at lecture notes i gathered that the three step process is:
If Alice wants to send x to Bob

1. Alice encrypts x with her public key and sends to Bob
2. Bob encrypts that with his public key and sends that to Alice
3. Alice decrypts x^(ab) and sends it to Bob

then he can decrypt using his private decryption key

[wooden glen]

Um, there are no public keys involved in plain Diffie-Hellman.

[wintry locust]

not public keys sorry, private keys

[wooden glen]

Not that either. The basic Diffie-Hellman scheme assumes that both Alice and Bob know who they're talking to -- or at least that with means external to DH they can verify that the messages each get from are in fact from the other party. The goal is to invent a secret that they will both know, but an eavesdropper who reads all their messages cannot feasibly know.

In practice, the "verify the messages come from the right other party" is generally done with some public-key cryptosystem, but that is not part of the DH calculations as such.

I think you may be confusing it with a description of RSA?

[wintry locust]

possibly

although the implementations I came across describe it in the same way I did, except private keys not public

so they say Alice and Bob will each have their own private keys which are inverses of eachother

that way ultimately Alice can send Bob the message (or key) which is encrypted using his private key

so he will have the resources to decrypt it

[wooden glen]

The reason why I'm confused is that the bare-bones Diffie-Hellman I'm aware of has only two messages:

1. Alice and Bob agree in advance on a prime, p, and a primitive root, g. These are not secret.
2. Alice chooses a random number a and sends g^a mod p to Bob.
3. At the same time, bob chooses a random number b and sends g^b mod p to Alice.
4. Each of Alice and Bob can now compute g^(ab) and use that as their shared secret.

I can easily imagine embellishments where there's a third message -- but there are many possible variants of that, so without knowing more, I'm not sure how to interpret the problem statement you posted.

[wintry locust]

that algo is also given in the lecture notes but named as the Diffie-Hellman Key Establishment as opposed to DH Exchange Scheme

[wooden glen]

Anyway, if we assume your original equations are a fair representation of the protocol you're describing ...

99, 48, and 18 are all primitive roots modulo 101, so we know that a and b must both be coprime to 100. In particular, a has a multiplicative inverse c. Raise your two first equations to the c'th power:
99^c == x^ac == x (mod 101)
48^c == x^abc == x^b == 18 (mod 101)
So you can brute-force the whole thing in one go, by computing successive powers of both 99 and 48. When the power of 48 ends up being 18, you know you've found the power where 99^c is the original x.

Wait, that is nonsense.

No it's not.

[wintry locust]

I feel like I may be misunderstanding the question or something because I can't imagine they would want me to brute force an answer

unless it's quite an obvious answer

[wooden glen]

Hmm? If you're only told the messages exchanged, then you're basically an eavesdropper, and there should not be a strategy an eavesdropper can follow that's significantly better than brute force. At least not something that's elementary number theory. But the quite small modulus also feels like it's selected to make brute force feasible.

[wintry locust]

ahh right, forgot about that for some reason

[wooden glen]

If you have a calculator or programming language that can do bignum arithmetic, it's not that onerous to simply start trying values for c:

$ python3
Python 3.6.9 (default, Mar 10 2023, 16:46:00) 
[GCC 8.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 48**3 % 101
98
>>> 48**7 % 101
28
>>> 48**9 % 101
74
>>> 

and so forth.

[wintry locust]

yeah pretty easy to automate

[wooden glen]

(And even then you can speed it up a bit by being observant along the way. Note that 48^3 == 98 == -3, so if you can find d such that 48^d == 2, we must have 48^(3+3+d) == 18. Lo and behold, the very next step in the sequence gives 48^11 == 8, so if only we can find a cube root of that, we're home free. But now 48^111 == 8 too, and 111/3 = 37, so 48^37 ought to be 2.)

[wintry locust]

this is what I got following your explanation

x = 0
n = 0
while x != 18:
  n += 1
  x = 48**n % 101
print(99**n) # 15

[unkempt fossil]

when is the sum of two consecutive squares a square?

[grave perch]

Those are almost isosceles Pythagorean triples.

Recall the formula.

$$(x,y,z) = (m^2-n^2, 2mn, m^2+n^2).$$

Now call $(m,n)$ as generator of $(x,y,z)$.

[sterile pumice]

wilfred9752

[unkempt fossil]

Do pythagorean triples cover all positive solutions of a^2 + b^2 = c^2?

[grave perch]

$(x,y,z)$ is an almost-isosceles Pythagorean triple if $(m,n)$ are consecutive Pell numbers.

[sterile pumice]

wilfred9752

[grave perch]

An example is the generator $(m,n) = (5,2)$ which generates $(20,21, 29)$.

[sterile pumice]

wilfred9752

[unkempt fossil]

Does there exist an infinite amount of

solutions

[grave perch]

Yeah.

[unkempt fossil]

what about

When is 2k(k + 1) the product of two consecutive numbers

[grave perch]

As far as I remember, there's this one recursive solution.

[unkempt fossil]

Im working on this diophantine equation which ive reduced to

m^2•(m^2 - 1) = 2k(k + 1)

[grave perch]

2k^2+ 2k = x(x+1) = x^2+ x
2k^2 + 2k = x^2 + x.
x = 2k (1)
x^2 = 2k^2 (2)
=> (x,k) = (0,0).

[unkempt fossil]

where did x = 2k come from

[boreal lagoon]

This is stupid, but why does it follow that (x,y,z) is proportional to this triple (these are integers)? The equality implies x/z=m^2-n^2/m^2+n^2 and y/z=2mn/m^2+n^2, but I just don't see that there should be a d\in Z such that (x,y,z)=d(...). What if 2/3=4/6, it doesn't follow that (2,3)=d(4,6) for d\in Z, right.

[primal pewter]

@boreal lagoon (x,y,z) being proportional to (a,b,c) simply means x/a=y/b=z/c, which is the case

no requirement for the common value to be an integer

[scarlet smelt]

Sorry if this is the wrong channel for such a query, but in a sequence like this (t1 = +ve number, t2 = -ve number, other terms are the sum of the previous two terms), in this particular case, the first 4 terms alternate signs. How do I find a sequence where the first n terms alternate signs?

[boreal lagoon]

Oh, I assumed there must be some integer that scales one of the triples to the other, lol. Thanks.

[primal pewter]

the ratio being an integer might depend on some other information that are not shown in the picture

[boreal lagoon]

There's no extra information here I think, it's a classification of Pythagorean triples (via Hilbert90).

[vestal rapids]

My book uses the euclidean algorithm proof to show by contradiction of minimality that d is the smallest element of such a set. I thought of another proof, is this proof correct? Is there anything missing to it?

[patent acorn]

you appear to have proven the stronger statement that in fact any common divisor of two numbers is equal to their gcd

so for instance if we take a = 12 and b = 16, then since these are both even numbers, c = 2 is a divisor of both of them, and it follows that gcd(12, 16) = 2
c = 4 is also a divisor of both of them, so gcd(12, 16) = 4
therefore 2 = 4

...so yeah probably you did something wrong

[vestal rapids]

Oh damn… where did i go wrong with this

[patent acorn]

well since we have a concrete counterexample we can actually just run through the proof and see where it turns a true statement into a false statement

[vestal rapids]

Eh wait but i did say gcd(r,s)=1. For the a=12 and b=16 case gcd(r,s)=2 no?

[patent acorn]

yep, r = 6 and s = 8

so definitely there's something wrong by that point

the actually minimal linear combination (well, one of them) is x = -1, y = 1, to get -12 + 16 = 4

and in that case, looking at rx + sy, you get 2, which is not 1

so... yeah i think you're wrong about rx + sy being 1

[vestal rapids]

does it help if i changed the wording :We claim that the only way rx+sy=1 is if gcd(r,s)=1

Because for the r=6 and s=8 their gcd is not 1 though it's 2

[patent acorn]

well that's true but now the rest of the proof doesn't work, because "if gcd(r, s) is not 1 then rx + sy is not 1" doesn't show that gcd(r, s) = 1 which is what you need for the next step

but yeah it is correct that if rx + sy = 1 then gcd(r, s) = 1

[vestal rapids]

But we picked rx+sy arbitrarily to be 1 because it's what we require for the minimal element of S, no?

[patent acorn]

except we just saw that rx + sy might not be 1

in the case of a=12, b=16, c=2

in fact if c = 1, which is a divisor of both a and b, then rx+sy is just whatever ax+by is, and the minimal element of S might not be 1

[vestal rapids]

wait sorry i'm still not getting it :")

We claim that the only way rx+sy=1 is if gcd(r,s)=1. then i proceeded to show that c has to be d. Therefore, this common divisor c has to be the gcd in order to be the minimal element of this set. So picking c=1 and c=2 is not valid because they're not the gcd of 12 and 16?

[patent acorn]

then i proceeded to show that c has to be d
(the problem is that your argument to show that isn't valid)

So picking c=1 and c=2 is not valid because they're not the gcd of 12 and 16?
...why would that make it invalid

it does mean that the result you get is completely wrong, but the proof does not assume that c must be the gcd of 12 and 16, only that c must be a divisor of a and of b, so it's valid to apply the proof whenever that's true, so c=1 is fine

otherwise it's like claiming that all integers are even, and then when someone presents the number 3 as a counterexample, you say applying it in that case isn't valid because 3 isn't even

[vestal rapids]

does it change anything when i changed the last sentence?

here i'm saying that you can choose your c but the one that will be the smallest element of S is d.

[primal pewter]

say the first two terms are x[1]=a>0 and x[2]=-b<0
see by induction that x[n] (for n>=3) is F[n]a-F[n+1]b, where F[n] is the n-th Fibonacci number (to have the indexing clear: F[1]=1, F[2]=1; we can also allow F[0]=0, but this is not important here)

so what you want is x[k]>0 for odd k and x[k]<0 for even k
that is a/b > F[k+1]/F[k] for odd k and a/b < F[k+1]/F[k] for even k
you want this to happen from 3 to n, so the conditions are

a/b > max{F[4]/F[3], F[6]/F[5], ..., F[2floor(n/2)]/F[2floor(n/2)-1]}
a/b < min{F[5]/F[4], F[7]/F[6], ..., F[2floor((n+1)/2)-1]/F[2floor((n+1)/2)-2]}

study the sequences (F[2t+2]/F[2t+1]) and (F[2t+3]/F[2t+2]); you might need Cassini's identity for this
I've got that the first one is increasing, while the second one is decreasing

so you have the necessary and sufficient condition M > a/b > m, where
M=F[2floor((n+1)/2)-1]/F[2floor((n+1)/2)-2]
m=F[2floor(n/2)]/F[2floor(n/2)-1]

Choose a/b such that a/b = (m+M)/2 and you have a sequence.

[patent acorn]

...ok i am still confused about where you got rx + sy = 1

are you saying that follows from ax + by being minimal in S? since it doesn't, take c = 1, a = 12, b = 16

...also i just have no idea where the last sentence came from
if c(rx+sy) is minimal (in what...?) then c = gcd(a, b)
therefore, gcd(a, b) is the smallest element of S
how does that follow at all you are skipping over several steps there

[vestal rapids]

oh i get it

i'm quite sure this stems from that arbitrary picking of c

ah yeah ok

thank you @patent acorn

[scarlet smelt]

thank you so much! I understand now

[scarlet smelt]

Also, given a starting integer, what negative number must be picked in order to make the alternating part of the sequence as long as possible? Let's say the sequence starts with 10, or maybe n, then what would the following negative number be?

[primal pewter]

we can't make the alternating part "as long as possible", because, as I showed above, this can be arbitrarily large

[scarlet smelt]

Hm. What if we have, say, 10 instead of n as the first integer?

[primal pewter]

sorry, I was wrong;
indeed, if we fix the first term, there should be an answer

[scarlet smelt]

Could you please elaborate on this?

[primal pewter]

I'm still trying to figure it, but the point is that n cannot be arbitrarily large, because by passingg to the limit in the inequality M>a/b>m, we would get that a/b is irrational, which is false

basically the condition that I found above, namely F[2floor((n+1)/2)-1]/F[2floor((n+1)/2)] > a/b > F[2floor(n/2)]/F[2floor(n/2)-1] is necessary and sufficient to guarantee that the length is at least n;
if we want this n to be maximal, than x[n+1] must break the rule, so we should add the condition that (-1)^(n+1)x[n+1]>=0

I don't really see it, but the central idea is to make the ratio a/b as close as possible to lim(F[n+1]/F[n]) = (1+sqrt(5))/2

for a=10, you should pick b=6 I think

[scarlet smelt]

hm

[white lion]

if an integer n is a pseudoprime to base 2 doesn't it neccesarily follow that it's a pseudoprime for every base a>2?

its easy to show this with induction with the base case 2^n = 2 (mod n)

and let it be true up to a, a^n = a (mod n), we know that (a + 1)^n = a^n + 1 (mod n) and by our hypothesis we have that (a + 1)^n = a + 1 (mod n) as needed

[normal heart]

And why is (a+1)^n=a^n+1 mod n?

[white lion]

binomial theorem

oh right it only holds for prime numbers

so why is being a pseudoprime to base 2 so special

[wooden glen]

is it, though?

[white lion]

If n is an odd pseudoprime to base 2 then so is m = 2^n - 1. (Theorem for infinitely many pseudoprimes to base 2)
The argument from what I’ve read doesn’t really use the fact that n is odd, for those familiar with the theorem is it possible to omit this assumption or am I missing something?

[wooden glen]

There are no even pseudoprimes to base 2. If n is even and positive, then 2^(n-1)-1 is odd and therefore definitely not a multiple of n.

[white lion]

akshually 🤓

that's not correct in 1951 the dutch mathematician N.G.W.H Beeger proved it to be true

[white lion]

i dont think theres a need to use the 2^n -1 part it was just used for trying to prove there are infinitely many odd pseudoprimes to base 2

[wooden glen]

Sorry, that should have been 2^(n-1) - 1. Will fix.

As in, the definition of "base 2 pseudoprime" is a composite number n such that 2^(n-1) == 1 (mod n).

[white lion]

hmm, is that the correct definition? Im familiar the definition that n is a pseudoprime base 2 if 2^n = 2 (mod n). the definition would be equivalent only if the inverse of 2 exists which may not always be the case

[wooden glen]

It's the definition Wikipedia gives.

(Except that article also explicitly assumes the number is coprime to the base -- but with that requirement it is trivial that base 2 pseudoprimes are always odd, anyway).

[scarlet smelt]

how can I solve this 🤔

[torn escarp]

looks like you're meant to experiment and try it out and see

[scarlet smelt]

I tried, but didn't get anywhere...

[west glade]

well where did you get

[torn escarp]

send pictures of scratch work, like we need to see some doodling out lines on grids and stuff, otherwise we have nothing to work with to help you out

[surreal tangle]

1. try setting up a coordinate system
   2)find out how to map a point with integer coordinates to the right letter(hint: look mod 3)

[brave citrus]

I know that if 2^a-1 divisible by 2^b-1 then 2^(a.c)-1 will divisible by 2^b-1 (a,b,c is positive integer), but i wonder if 2^(a.c)-1 divisible by 2^b-1 so what conditions do I need to add so that 2^a-1 is divisible by 2^b-1?

[primal pewter]

this might be helpful: gcd(2^m - 1, 2^n - 1) = 2^gcd(m,n) - 1

in particular 2^m - 1 | 2^n - 1 <=> m | n

[brave citrus]

Thank you. But i wonder if it still exists any more conditions?

[surreal tangle]

You don't need anymore, since it's an if and only if condition

[brave citrus]

Oh thank you for your help

[surreal tangle]

Dont forget to thank filip

[brave citrus]

yes,i know

[keen pagoda]

just out of curiosity
is there an easier way of finding multiplicative inverses in Zmodp than doing the euclidian algorithm to find 1 as a linear combination of p and the number?

actually the process isn't that long

but idk

[cold tendon]

@keen pagoda more aesthetic way a^(p-2)

But its more difficult

[keen pagoda]

lmao

indeed more aesthetic

this is from fermat right

theorem

cus a.a^p-2 = a^p-1 = 1modp

[cold tendon]

Yeah

$$ (Z/pZ)^* $$

[sterile pumice]

A shot

[cold tendon]

Ooh

How to prove that it is cyclic group?

I have the proof but is there a more appealing way?

[keen pagoda]

under multiplication?

[surreal tangle]

All elements from 1 to p-1 can be generated by multiplying by that number which you want to generate

[keen pagoda]

oh yeah the star is multiplication

[cold tendon]

Yeah multiplication and coprime

[surreal tangle]

No it excludes 0 afaik

[keen pagoda]

I read somewhere every finite field is cyclic or something similar

let me find it

[cold tendon]

No

For example

Okay i dont know

[cold tendon]

What that number?

[surreal tangle]

every element can be generated by multiplying 1 by the appropriate number

[wooden glen]

The multiplicative group of a finite field is always cyclic.

[keen pagoda]

curious if I can prove this

I'll try thinking about it later

probably won't cus I'm in like chapter 3 probably don't have the tools

but who knows

maybe it's easier

[cold tendon]

I dont understand what you mean

[surreal tangle]

What is a cyclic group?

[keen pagoda]

cyclic under multiplication not addition

addition is obvious

it's true almost by definition

multiplication is a whole nother thing

[still flare]

This isn't the right context. (Z/pZ)* is not written additively — 1 is the identity in this group, so performing the group operation on 1 several times would do nothing.

[cold tendon]

Yeah

[still flare]

You are confusing the additive group of the ring Z/pZ with the multiplicative group (Z/pZ)* — aka the group of units of Z/pZ.

[surreal tangle]

I was under the impression this was under addition. For multiplication its a lot more complicated

[still flare]

Yeah you don't say!

[cold tendon]

Sorry i should say it at the begining

[still flare]

No, it's not your fault

Most people know this notation

[surreal tangle]

Z*p is also used sometimes but yeah

[still flare]

Tropo alluded to a more general fact here, and I think I'll elaborate more

[sterile pumice]

Boyt

[still flare]

You say you know a proof already that (Z/pZ)* is cyclic. Frankly I don't know a particularly pretty proof of this fact, but you should realise that exactly the same proof works for the fact that I state above.

So perhaps that will be more pleasing than simply showing it in this narrow case.

This also explains how, for example, why (Z/15Z)* isn't cyclic — or at least that it has no necessity to be.

[cold tendon]

There is elementary proof for this concrete example

?

[still flare]

You said here that you had a proof; now generalise it as I indicated

[cold tendon]

I want prove it only with number theory

[still flare]

OK

[cold tendon]

Yeah i want another versions thank you for giving

[wooden glen]

Oh, neat.

[cold tendon]

@still flare I found this problem in M. Ram Murty Problems in Analytic Number Theory

[wooden glen]

4, 11, and 14 all have order 2 in (Z/15Z)*, and a cyclic group has at most one order-2 element.

[cold tendon]

Ok

[keen pagoda]

just realised I don't know a proof that Z/pZ is cyclic

I know about fermat's little theorem but idk if it implies some element can't have any smaller order

[wooden glen]

Do you mean (Z/pZ)*? The additive group of Z/pZ is cyclic almost by definition.

[keen pagoda]

yes

I'll see if I can prove this

maybe just go ahead and find the number in question

the generator

my intuitive guess is p-1

oh no

p-1 is -1 lmao

[wooden glen]

That's what Artin (right?) said he was postponing until chapter umpteen, wasn't it?

[keen pagoda]

(right) he actually will prove the case for all finite fields

and probably do a collorary

ig

[wooden glen]

I don't think there's a simple direct way to compute a primitive root modulo p. In practice the usual recommendation is to try elements randomly until you find one -- there's generally lots and lots of them.

It's easy to check whether you're looking at a primitive root (aka a generator of the multiplicative group): if x^((p-1)/q) != 1 for all primes q dividing p-1, then x must have order p-1 in the multiplicative group.

[keen pagoda]

oh

[still flare]

Hint: suppose it weren't cyclic, and let k < p-1 be the highest order of any element. Try to find a contradiction here.

I agree with Tropo, I don't think you can identify a generator from the outset.

I'm not aware of any way to do so actually... surely there's a nice algorithm but I just don't know it

[keen pagoda]

I feel like there isn't tbh

[wooden glen]

Artin eventually proves cyclicness of the multiplicative group by appealing to the Structure Theorem for f.g. abelian groups.
It can be done more elementarily by careful accounting for how many elements of each order there can be.

[keen pagoda]

ty

ig I can somehow construct an element with higher order with that maybe

[still flare]

That's the idea

[keen pagoda]

hm

I'm good with numbers I can do it

oh well now that's the thing that will disturb me for the next hours or less until I find the proof

[still flare]

Remember that for any group G, if and element x has order < |G| then there is some y not in <x>.

[keen pagoda]

👍

[still flare]

I know that sounds super trivial now that I say it but it is helpful

[keen pagoda]

it is actually

since if I only use stuff in <x> then I can't get any further just thinking about the exponents since they will just sum

ty

no more hints pls

well let a be this number and b its order
(a.c)^b = c^bmodp

that's probably helpful

[foggy shell]

I'm trying to remember what a primitive root is here, isn't an element whose residue class is the whole ring?

[keen pagoda]

that actually seems to be the only thing that may help me since in a number theoretic perspective it's very hard to think of what p-1 has of special

as an exponent

[wooden glen]

"Primitive root" means a generator for a cyclic subgroup of a multiplicative group -- in the case for the entire multiplicative group.

[foggy shell]

alright thats what I was thinking but not with the right words

working on my formal math rtraining

[keen pagoda]

starting to have an idea

maybe I can get a number with order that doesn't divide b

[still flare]

There's nothing special about p-1. This is a fact about fields, not primes.

[keen pagoda]

oh yeah

[keen pagoda]

so actually ig I should use a sum somewhere

maybe

or not idk if I have to use everything about fields

but it would feel weird to prove such a big property about fields without using sums

[still flare]

You'll want to look at polynomials

[keen pagoda]

so sum and multiplication

[still flare]

Sure.

[keen pagoda]

sucks that the only thing I know about fields is that they have characteristic 0 or prime

I have no knowledge about any theorems

I'm trying to see a simple case cus it seems like it would be fruitful

suppose the heighest order is 2

a is the element of highest order and idk it's mod5
and c is not congruent to 0
(a+c)² = a² + 2ac + c² = 1 + 2ac + c² = 1 + c(2a + c)
so 5|c(2a + c)
so 5|2a + c
maybe I can get something out of this

[primal pewter]

the highest order of an element modulo p is always p-1

by primitive root theorem

[keen pagoda]

I know that's what I'm trying to prove

I'm trying to arrive at a contradiction from this

[foggy shell]

I'm pretty sure it does imply that an element can't have a smaller order.

[keen pagoda]

in principle it doesn't seem to do so

I mean it's just an application of the fact that a^|G| = e

for any finite group

[primal pewter]

indeed, it doesn't imply that

take the element 2 in modulo 7

its order is 3

[keen pagoda]

oh yeah there's that

what I'm trying to prove is that some element can't have a smaller order

[foggy shell]

what if all elements had a smaller order

would that imply that p isn't prime?

[keen pagoda]

idk

since this is a general property about fields, that they're multiplicatively cyclic, it shouldn't be a property about primes

ig

[primal pewter]

it's just for finite fields

[foggy shell]

I'm pretty sure its shown that all finite element fields have a prime number of elements

[patent acorn]

they all have a prime power number of elements

[keen pagoda]

ye ye

[foggy shell]

whats that theorem called I feel like thats a fun proof

[primal pewter]

not sure if it has a name, but it follows from Cauchy's theorem

[keen pagoda]

that there's one element of each prime divisor order?

[primal pewter]

yes

[keen pagoda]

I think I'll continue try proving that thing later I'm not getting anywhere

that they're cyclic

maybe that sum just isn't what I'm supposed to do

[primal pewter]

the proof is about counting elements by their orders, as far as I remember it

and some inequalities that become equalities

[keen pagoda]

I had a small little piece of an idea that may help

if I do like
ax^n + ... + a^n+1
which is
a + a²x^n-1 + ... + a^n+1
a(1 + ax^n-1 +...+ a^n)
that seems like it would only be obviously of at most order n if a was a power of x

maybe I could prove if it's not, it isn't

wait actually not obviously

forgot the second term lol

[wooden glen]

The important fact of fields is that a polynomial of degree n can have at most n roots in a field.

[keen pagoda]

this is true about all fields?

[wooden glen]

Yes. All integral domains, in fact, but a finite integral domain is a field anyway. :-)

[keen pagoda]

well it makes sense the proofs about polynomials seem to not think about the numbers at all

very algebraic

ig that's why the field generalization is cool, a lot of proofs are just algebra

algebraic manipulations

[wooden glen]

Further hint: ||if the order of some element a divides n, then a is a root of x^n-1||.

[keen pagoda]

I'll think of grabing the hint later if I get more stuck than I am

I'm thinking if there's any properties about a polynomial being or not factorable that'd be useful

actually I had an idea

based on the n roots thing

maybe

I could make a polynomial +1

and the roots would be when the polynomial +1 is the identity

and that may have something to do with the order

[wooden glen]

What's the main property that defines "order"?

[keen pagoda]

any smaller exponent is distinct?

[wooden glen]

The even mainer one. :-)

[keen pagoda]

if you're not asking for the literal definition that is it for me

that a^n for any smaller n isn't 1

[wooden glen]

The mainer one is that a^n is in fact 1 for that n.

[keen pagoda]

oh

cool ig

maybe I could think of which other elements would be able to be 1

AAAAA

I think I ascended wait

don't say anything let me cook

a^n - 1 = 0 specifically for a

and

there's at most n-1 other elements which could have this order or a smaller multiple

which uhh

would obviously mean something

surely

if n = the order that'd go right in

[wooden glen]

At this point you may observe that if a satisfies x^n=1, then every power of a does too.

[keen pagoda]

oh

and each element should be distinct

so it's all of them

pls don't give me any other hints that feels close

too close

so the solutions are all the n powers of a

the only ones in fact

so any non-power of a I put in should not solve this

so like, (c.a)^n = c^n which is definetely not 1

which is an advance from what I started with lol

wait wait I think I'm basically there

could c.a have a smaller order?

no no

because

[wooden glen]

Definitely a good direction here.

[keen pagoda]

(c.a)^k = c^k.a^k
for some smaller k
(c.a)^l for any l less than k should too

I think i'm getting into some argument

[wooden glen]

I'm not sure whether the reasoning about c leads somewhere, though.

[keen pagoda]

c is some number which isn't a power of a

I want to build some element that has a higher order from some number which is not a power of a

[wooden glen]

For what it's worth, what I had in mind was not as constructive as that.

[keen pagoda]

well the other person also talked about polynomials

and was suggesting constructing

ig

and tbh the only thing about polynomials that seems to be useful is this

theorem

about roots

[wooden glen]

I admit I'm not exactly sure what Boyt had in mind when he spoke about constructing some other element.

[keen pagoda]

hum

I came to some conclusion I'm not sure of

[wooden glen]

You have shown that if there is one element a of some order, then all elements of that order in the field are powers of a.

This is pretty relevant.

Can you also derive how many of them there are? (I.e. excluding ones whose order merely divides the order of a).

[keen pagoda]

how many of them what

how many of who

[wooden glen]

How many elements of the field have order exactly the same as a?

[keen pagoda]

oh

it's that thing about cyclic groups isn't it

[wooden glen]

Yes, if by "that thing about cyclic groups" you mean the appropriate thing. :-)

[keen pagoda]

phi(n)? (I'm not sure if it's that that's just my gut feeling I need to re-derive that thing because I know it exists)

[wooden glen]

Bingo.

[keen pagoda]

oh right

I'm literally shaking I'm kinda confused

[wooden glen]

Sorry.

[keen pagoda]

suppose this l is the order of c
(c.a)^l = a^l
a^l.k = 1
which means (a^k)^l = 1
and I forgot what my conclusion about this was but I'm gonna let this registered

[keen pagoda]

this l

sooo phi(n) elements have this order, exactly, precisely, specifically

coooool

amaaaaaaziiing

[wooden glen]

(But remember that this started with the assumption that we have some element of the given order. So what we now know is that for each n <= p-1, there are either exactly phi(n) elements of order n, or none).

[keen pagoda]

sure

well any n should divide p-1

[wooden glen]

That too.

[keen pagoda]

is there any property about phi of something that divides something maybe

well actually actually

by cauchy all primes that divide p-1 have some element with their order

and phi(q) = q-1

which I'm not sure of what to make of this I just think this is cool

supposedly p-1 doesn't matter so ig just: some primes have this cool property

[wooden glen]

In case you want another hint: ||Consider the cyclic group of order p-1. Ignoring the question of whether it's isomorphic to the multiplicative group or not, how many elements of each order does that cyclic group have?||

[keen pagoda]

I will, probably

idk if I'm as motivated as before to get a proof in my own

[wooden glen]

That sounds like your cue to sleep on it. :-)

[keen pagoda]

what is "sleep on it"

(not a native english speaker)

[wooden glen]

It means stop thinking actively about the problem until tomorrow -- let your subconscious work on it while you sleep.

[keen pagoda]

oh yeah

my brain is frying that probably is what I should do

one time my brain was frying with a specific geometric proof I wanted to do then I slept and immediatly got it when I woke up

(it was that the diagonal of an isosceles trapezoid always made a 45º angle, I specifically wanted to derive it from constructing an isosceles trapezoid from a square for specific reasons)

wait was it this?

not sure

is this even true???

[wooden glen]

A rectangle is a special case of isosceles trapezoid, and the diagonals of a rectangle can intersect at any angle you want ...

[keen pagoda]

ok I forgot what was the specific type of iscosceles trapezoid

because it is one

which I found out I could build from a square

and the proof the construction works was one of my biggest big brain moments

[wooden glen]

Nice.

[keen pagoda]

the reason I did that is that an exercise a teacher gave me was to find the angle
then I said "works for a square lol" and he said squares aren't trapezoids so that wouldn't work
so I got from a square to that out of spite

[wooden glen]

If the sum of the parallel sides in your isosceles trapezoid is twice the height, then each diagonal would be 45° to the base.

[keen pagoda]

I have the picture of the proof but forgot what I was proving 😭

[keen pagoda]

IT WAS THAT INDEED

aka the avarage of the the paralel sides is the height

[wooden glen]

Yes.

[keen pagoda]

I remember I used something about avarages

geometrically

[wooden glen]

And there's a neat proof involving a centered square of the same height, so that checks out.

[keen pagoda]

welll it wasn't the same height but I made a square and alongated its diagonals, then choose two points in the alongated lines to be the vertices of a new trapezoid
I then proved the fact by proving the new trapezoid had that property and the angle thing came easily because the base was paralel to the square's
then I hand-waved a "by making a big enough line I can get to any trapezoid angle so it can construct any other"

oh yeah, I proved that drawing a paralel line in the middle of the trapezoid (which by some theorem is the avarage of the bases) would give the same size as the height, somehow

found out

that's not the apropriate place I'll post the fun little proof in #geometry-and-trigonometry

[keen pagoda]

posted it there

[iron edge]

Can the left hand side of or the entire equation
[ \gcd(\gcd(a, n), \gcd(b, n)) = 1 ]
be simplified?

[sterile pumice]

A Lonely Bean

[white lion]

simplified in what way?

[iron edge]

By somehow getting rid of the nested gcd

If that's possible

[wooden glen]

Do you consider writing simply gcd(a,b,n) to be a simplification?

[iron edge]

Oh, why didn't I see that

Yes that certainly is better

Thank you

[white lion]

you're welcome

[iron edge]

In that case I wonder if there is a name for the function counting the solutions to gcd(a, b, n) = 1 for fixed n and 1 <= a, b <= n

[patent acorn]

...no it doesn't

gcd(2,4,5) = 1, gcd(2, 4) != 1

[iron edge]

gcd(2, 2, 1) = 1

[white lion]

oops you're right nvm

[keen pagoda]

soooo

need to arrive a contradiction

x^n = 1mod p has n solutions which are each powers of a

which means there can only be one element of the heighest order

no no

does it?

no no

that means that only elements in <a> have the heighest order

so ig I could prove there is a c outside of <a> that would also have the heighest order

because I know there is a c outside of <a>

there are phi(n) elements with that heigher order, the others being just exponent multiples of those

[still flare]

The solutions to x^n - 1 are those elements whose order divides n.

[keen pagoda]

maybe I could start by something like "let c be the element not in <a> with the heighest order" or something

[keen pagoda]

ye ye

[primal pewter]

there's no need to search a contradiction

[keen pagoda]

don't tell me the proof pls

[primal pewter]

I'll just reiterate something you proved yesterday

[keen pagoda]

oh

[primal pewter]

you proved that there are either 0 or phi(d) elements of order d

[keen pagoda]

sure

[primal pewter]

and I think you proved that if d does not divide p-1, then there are surely 0

[keen pagoda]

yeah but that's just a group theory fact

[primal pewter]

indeed

[keen pagoda]

and idk if it'll help

[primal pewter]

it will

[keen pagoda]

but like p-1 itself doesn't matter right

I can just say idk george

d must divide george where george is the field's size

[primal pewter]

yeah, sure, you can say |K|=q, with q not necessarily prime, and then you have q-1 instead of p-1

[keen pagoda]

ok it doesn't matter I need to forget this

[primal pewter]

so if we switch to q (which is a power of a prime, but it doesn't matter), then the orders can only be divisors of q-1, by that group theoretic observation

[keen pagoda]

yes yes

but ig I can just pretend q-1 is q cus that -1 is annoying

and shouldn't change anything

[primal pewter]

ok, let's say q instead of q-1

so the possible orders are divisors of q

[keen pagoda]

yes yes

so n for example

which is the supposed highest order

so the greatest divisor of q which is an order

maybe I could prove there is another order k that divides q but not n

I'm still on the c.a idea cus I have no idea of another way to go

it seems like you and troposphere are trying to make me count stuff

but I have no idea how that could lead me to anything

lots of troposphere's questions yesterday were about counting stuff

[primal pewter]

yes, counting will be useful

[keen pagoda]

so I have phi(n) elements of order n, n which divides q

[primal pewter]

the thing is that observation that there are either 0 or phi(d) elements of order d, for ever d | q

the goal is to remove that 0

[keen pagoda]

but it was removed by assumption

ohhh

I get what you mean now

thought you were saying another thing

damn that seems difficult

well yeah that would completely prove this

so x^d = 1, I should prove that if d|q, this has a solution

[primal pewter]

here is a hint to get things started: which were the possible orders, again?

[keen pagoda]

the ones that divide q

[primal pewter]

right

so let's list them

[keen pagoda]

d1, d2, d3... dn :D

[primal pewter]

here n=phi(d)

phi(q)

[keen pagoda]

ye ye

[primal pewter]

ok, so
there are either 0 or phi(d1) elements of order d1

there are either 0 or phi(d2) elements of order d2

and so on

can you get an upper bound?

[keen pagoda]

for what

[primal pewter]

for elements of any order

[keen pagoda]

supposedly only phi(di)

but I mean I think what I should get is a lower bound

greater than 0

[primal pewter]

I'm not sure about lower bound

[keen pagoda]

I only know that for the prime orders this is indeed phi(di)

cus of cauchy

which tbh I never saw a proof so I feel weird using it

[primal pewter]

for the moment we only need that there are at most phi(d1), phi(d2) and so on

[keen pagoda]

wdym get an upper bound phi(di) is the upper bound

[primal pewter]

no, we don't get any further upper bound

[keen pagoda]

the only smaller upper bound could be 0

[primal pewter]

so for the moment we only replace "0 or phi(d1)" with "at most phi(d1)"

[keen pagoda]

but only if it was 0

hm

[primal pewter]

and then we count them together

[keen pagoda]

like I should pretend idk about 0 yet

so I get a lower upper bound

[primal pewter]

by upper bound I mean that whether there are 0 or phi(d1), we know for sure that there are at most phi(d1) elements of order d1

[keen pagoda]

oh

yeye that's the upper bound

[primal pewter]

and think about what happens when we count them together; like what we are actually counting

[keen pagoda]

ym count the elements of order d1?

[primal pewter]

I meant counting elements of order d1,d2,d3,...

all together

[keen pagoda]

oh

if d1 divides d2 that should be a subset of it right

like

I can only count the ones that don't divide eachother

no no

I'm confusing something

aaa I think I'll give up on this

will just leave this on my backburn for a while

[primal pewter]

we are basically organizing K* by sorting out elements:
those elements of order d1,
those elements of order d2,
and so on...

[keen pagoda]

I'll leave this in my backburner until I learn the proof for some other reason or accidently discover it cus I have made 0 discoveries until know

just united tips

hints

[primal pewter]

when you'll think about this problem again, I strongly suggest inspecting the case q=15
this might be helpful to get some motivation for the logic of the proof

[keen pagoda]

hm

ok

[primal pewter]

there is unfortunately some step that might be harder to see directly on the general set up; Troposphere anticipated that step with this hint

at any rate; I checked my Abstract Algebra notes to see how my prof proved this theorem back then;
apparently he used a clean algebraic proof which didn't require counting or euler totients, but just a small group theoretic argument instead

[bronze citrus]

Hi guys

[scarlet smelt]

In order to prove H. Steinhaus' Lattice-Point Theorem, how does one find the 'special' point P such that if a circle of increasing radius has its centre at P, it will have exactly n lattice points in its interior for all n > 0, n ∈ Z?

[primal pewter]

@scarlet smelt the idea is to fix the center P such that no two lattice points are at the same distance to P
in this way there exist the closest point to P (unique), the second closest point to P (unique), and so on... (all unique)

say P has coordinates (x,y)

you want x and and y such that (a-x)^2+(b-y)^2=(c-x)^2+(d-y)^2 implies a=c and b=d

[scarlet smelt]

I'm aware, but how do I find such a point P?

[scarlet smelt]

Yeah, I've done the proof

[primal pewter]

you want x and y such that a^2-2ax+b^2-2by=c^2-2cx+d^2-2dy implies a=c and b=d
i.e a^2+b^2-c^2-d^2 + 2(c-a)x + 2(d-b)y = 0 implies a=c and b=d

x=sqrt(2) and y=sqrt(3) do the job

I found them based on the fact that 1,sqrt(2),sqrt(3) are linearly independent over Q

[in other words, A+Bsqrt(2)+Csqrt(3)=0 with A,B,C rational, implies A=B=C=0]

there are different versions of the theorem; this proves that there is a disc with exactly n lattice points inside

but there is also a version with exactly n points on the circumference; I don't think I know how to find a center in that case

or the centers, actually

[scarlet smelt]

what does this mean?

[still flare]

Do you know what linear independence means in the context of vector spaces? This is exactly the same.

[scarlet smelt]

Yes

[primal pewter]

I explained that one line below

[sturdy thicket]

Is 1 coprime to every number? Cuz by the books im following the definition is (a,b) =1 then a and b are coprime.
If yes is it counted on the Euler s function

[still flare]

Yes

phi(1) = 0

Or well, let me elaborate.

It doesn't really matter what phi(1) is. You could define it as 0 if you take a certain perspective on the group of units of a ring... but we don't need this.

We could define it as 1 and have the nice multiplicative property still hold, so to be honest it would be a better idea to define phi(1) = 1

But this doesn't matter to the rest of how phi works

But yes, 1 is coprime to every number by definition.

[primal pewter]

phi(1) is just 1 by definition, not by convention

phi(n) = number of elements in the set {1,2,...,n} that are coprime to n

[still flare]

This is not a good definition of phi

You could equally define it as for the set {1, ..., n-1}, and for everything except n=1 we would agree, see?

The 'intrinsic' definition — which explains Euler–Fermat once you know some group theory — is that phi(n) = |U(n)|, where U(n) is the group of units of the integers modulo n.

[primal pewter]

with this definition you still get phi(1)=1

[still flare]

Hold on.

This is the reason it's weird for n = 1. When you look at the integers modulo n, you get the trivial ring, and it's not entirely clear how to define the group of units of the trivial ring.

For example, 0 is an element of this group of units, under one definition. This is unlike any other ring, in which zero divisors are not units.

If you want it to be a group, indeed it has to have one single element. But I'm sure you can see that this is a weird case, and it is not entirely clear from the definition.

[primal pewter]

you just have 0=1, so 0 is invertible

[still flare]

Yes.

[primal pewter]

so I still don't see what's wrong with phi(1)=1

[still flare]

I agree.

[primal pewter]

idk, maybe I'm just so used to statements that start like "Let R be a ring with 0=/=1..." [in contexts in which we assume rings have unity], that I simply think about the trivial ring as a ring in which 0=1;

and I don't think this is something wrong; I mean, the definition of a ring (with unity) never claims that 0 and 1 have to be different

and once we are fine with the fact that in a ring (with unity) with only one element we have 0=1, it follows from the definition of a unit that 0 is a unit; hence |U(R)|=1

[graceful sable]

so im working on this book called "number theory through inquiry" (great book btw so far im enjoying it) for fun and im proving every theorem i come across (also for fun)
Essentially to prove the forward conditional, i have

a congruent b mod n -> (1) a-b = nl, suppose a = nq_1 + r_1 and b = nq_2 + r_2, substitute these into (1) and we find n(q_1-q_2) + (r_1-r_2) = nl. Is it appropriate to match terms such that n(q_1-q_2) = nl and r_1 - r_2 = 0 which then shows r_1 = r_2? 🤔

[rustic tulip]

@graceful sable

[graceful sable]

?

[rustic tulip]

Have you proved this direction? If a and b leaves same reaminder upon division by n then a congruent to b modulo n

[graceful sable]

ive proved the foward conditional and reverse conditional using the method i outlined in my question

[rustic tulip]

Use this definition: $a \equiv b \pmod{m}$ iff m divides a-b

[sterile pumice]

.doc

[graceful sable]

That is what i'm doing (:

[rustic tulip]

sorry, i can bearly read

[graceful sable]

i think

[rustic tulip]

maybe you are already right

[graceful sable]

ah let me outline it in latex

[rustic tulip]

sure please

For one direction, you assume they leave same reaminder

for other assume they are distinct and use the definition of congruence

[graceful sable]

$a \equiv b \pmod{n}$ rewritten as $a-b=nl$. Let $a = nq_1 + r_1$ and $b = nq_2+ r_2$. By substitution we find $n(q_1-q_2)+(r_1-r_2)= nl + 0$. By matching terms, we find $r_1 -r_2 = 0$ or $r_1 =r_2$. (Forward conditional proved)

[sterile pumice]

Maestro Li

[rustic tulip]

can I edit a bit?

The idea is correct

a=b+nl

[graceful sable]

sure, what do you suggest?

[rustic tulip]

now use division algorithm on b

[rustic tulip]

then substitute here

from congruence a=b+nl

and by divison algorithm on b, b=qn+r,

now you see b leaves reaminder r, right?

now subtitute this into a and see what reaminder you get there

I’ll typeset again to show what I mean

Assume $a \equiv b \pmod{m} \implies a=b+nl$ for some n $\in \mathbb{Z}$

[sterile pumice]

.doc

[rustic tulip]

performing Euclidean division upon b, $b=qn+r, 0\leq r<n$

[sterile pumice]

.doc

[rustic tulip]

This means our remainder upon is r

$a=b+nl= (qn+r)+nl= n(q+l)+r$

[sterile pumice]

.doc

[rustic tulip]

This means a also leaves the same remainder ‘r’

[graceful sable]

ohhhh i see now, good idea!

[rustic tulip]

Your proof is not incorrect, but too many variables

I means it correct

All good

[graceful sable]

ah, those were those the equations given in the theorem lol, but it's reassuring to hear that my proof is correct

[torn escarp]

I like the orange

[rustic tulip]

Thank you

[wooden glen]

It's basically asking for one-dimensional subspaces of (F_3)^2 and (F_5)^2.

Oh, sorry. If you're in high school you have probably not seen abstract vector spaces yet. Have you see the definition of a "field"?

Good, and you have probably only seen plane vectors, i.e. pairs of real numbers that represent points in a coordinate system.
It turns out that arithmetic with integers modulo 3 (or 5 or 7 or some other prime number) makes another field.
So we can consider "vectors" where the entries are not real numbers but elements of, say, the field with 3 elements.
All in all there will then be 9 different vectors of that kind, and if we take the equations that make "lines" in the case of real numbers and interpret them in this new setting, we'll get something that sorta-kinda-but-not-quite behaves like plane geometry.
In Xuetao's problem it turns out that the nine classes of points it calls A, B, C, ...., H, I can be considered to be just the nine vectors of that kind. And it further turns out that straight lines on the paper correspond to "lines" in the 9-point geometry.

(That's a very quick sketch, I don't think I'll be able to fill in all the gaps in this medium, sorry).

For (2), the problem only speaks about lines through the bold A, so two different of those lines won't be parallel.
However, consider the line through bold A and bold H, versus the line through bold A and bold F.

For (1), what would be a line that passes through more than 3 different letters?

No, also the lightface ones. Consider the example in the problem of a line that passes through {A, F, H}.

[sacred junco]

how do i start with number theory

[coral venture]

read a book

[vocal quail]

I always recommend khanacademy.org, he does quite a bit of advanced math, not sure if number theory is on the list

[foggy shell]

Can someone explain what aspect of DES makes it a non-idempotent cipher?

[vocal quail]

If you do it twice, you don't get the same answer as if you do it once?

Idempotency: f(f(x)) = f(x)

[foggy shell]

yeah but what part fo DES gives it that property, is the the substitution boxes?

[vocal quail]

Oh, you mean the DES algorithm specifically?

[foggy shell]

yes

[vocal quail]

OK, sorry. I thought you were asking about the definition of idempotency, my mistake

[foggy shell]

you are good the phrasing could easily have that interpretation

[wooden glen]

"Idempotent" seems to have a specific meaning for cryptosystems.

[wooden glen]

In general, I don't think one would expect a Feistel cipher to be idempotent at all. So that's not something we can credit the S-boxes for.

[foggy shell]

kind of? an idempotent cryptosystem is defined as a crypto system where if you apply the encryption to a plain text twice with two different keys, its the same as applying it once with some other key.

A good example is the ceaser shift cipher. If I shift all the letters in a plain text by 4, then ecrypt it again by shifting them by 8, the resultant cypher text is the same as if I shifted the plain text by 12.

whats a feistel cipher?

[wooden glen]

https://en.wikipedia.org/wiki/Feistel_cipher -- a general architecture for block ciphers that DES is an instance of.

[foggy shell]

ahh

[foggy shell]

why wouldn't it be considered idempotent?

from what I can find online it says that applying a feistel cipher more times makes the system more secure, which to me suyggests that its non idempotent

[still flare]

A function f is idempotent if f(f(x)) = f(x) — you note that if f(—) represents a particular encryption method (if you like, with a particular key) then this is not what you have described.

It is really quite strange to me that this is called an idempotent cryptosystem, but I suppose a homomorphic cryptosystem is something else.

[wooden glen]

What he says seems to be consistent with the crypto meaning presented at e.g. https://www.khoury.northeastern.edu/home/riccardo/courses/csg252-fa06/lecture3.pdf

[still flare]

Addendum: this would be a really AWFUL property for a cryptosystem to have! It would mean that certain messages would never be encrypted, and simply remain the same!

[foggy shell]

idempotent in this case means that the plain texts are mapped to the same set of cipher texts with the same set of keys

[wooden glen]

A handwavy argument: It is generally recognized that Feistel ciphers become stronger by increasing the number of rounds. If DES were idempotent, it would mean that a large class of 32-round transformations (namely the ones whose key schedule is the concatenation of two independent DES key schedules) could all be expressed as a 16-round transformations, which doesn't seem to square well with an assumption that doing 32 rounds is stronger.

[still flare]

I know! :) you just talked about that. But I might point out that you [were a bit misleading](#elementary-number-theory message) earlier

[wooden glen]

That wasn't Catman.

[still flare]

I know :)

[foggy shell]

the phrasing is new to me so sorry for messing up a bit with it

[still flare]

but one doesn't typically respond yeah to the wrong definition

[wooden glen]

From the slides I found, it looks like the point is that there's a notion of composing entire ciphers (or rather, equivalence classes of ciphers under relabeling of keys), and the "idempotent" ones are the ones that result in a relabeling of the same cipher when it's composed by itself.

[foggy shell]

yeah, the fact that DES is a fiestel cipher is what makes it non-indempotent. So now I am left wondering what makes a feistel cipher non-indempotent

It can't be the switching of the left and right bits, which leads me to think it has to do with the XOR, or the function F of the key

[wooden glen]

At the end of the day, I'm not sure you will find a more enlightening answer than "because idempotency is a very special property that's generally only the case for ciphers with particularly simple data flows, and there's nothing about the structure of DES that looks like it would make it idempotent".

[surreal tangle]

Yes, 3 is the maximum possible

Your intuition for the first and second one is wrong
Here is a way of proving it mathematically: ||we'll be using rectangular coordinates.
Assign each integer coordinate in the box [0,2]x[0,2] a letter:
Let (0,0) = A, (1,0)=B, (2,0)=C,D=(0,1),E=(1,1), F=(1,2), G=(2,0),H=(2,1),(2,2)=I
. Now given any point, we can find its associated letter. Say we wanted to find the letter associated with the point (15,16). Reducing mod 3, (15,16)=(0,1)=D. So the point (15,16) is associated with the letter D. Now we have everything required to figure it out.
The line through A and H has equation y=2x. So every integer point on that line will look like (k,2k). Now mod 3, k can be only 0,1 or 2. So the line can only go through (0,0),(1,2) and (2,4)=(2,1). (0,0) corresponds to the letter A, (1,2) corresponds to the letter H and (2,1) corresponds to F. So the line will only ever pass through A,H and F. The line y=x has points of the form (k,k), and k can be 0,1 or 2 mod 3 so it can only pass through A, E and I. The lines x=0 and y=0 will pass through A,D,G and A,BC. The line 2y=x passes through the same 3 points A,F and H.|| You can extend this from mod 3 to mod 5 and mod 7

You can see that there are two non parallel lines through A which give the same set of letters {A,F,H} and no line passes through more than 3 letters

[surreal tangle]

Why wouldn't what work?

[sterile pumice]

smidgin

[patent acorn]

i'm pretty sure 2y = x passes through 6 points in a 6x6 grid

(0,0) (1,2) (2,4) (3,0) (4,2) (5,4)

the fact that there are only 3 y values doesn't really matter, there are 6 different x values so that's 6 different points

[surreal tangle]

My bad the x coordinate changes even if the y coordinate of 2 points are same

[patent acorn]

3y = 2x would be an actual problem though, the only solutions are (0,0) and (3,2) i think

[surreal tangle]

Yeah, 3y=2x is the right example

[patent acorn]

oh and also (0,2) and (3,0)

but still that's 4 points and not 6

so yeah 3y = 2x shows why it doesn't work

i think the thing that actually breaks it for non-primes is that you can have things like "3y = 2x" instead of stuff that just looks like "ny = x"

for a prime number it's a field so you can always turn it into ny = x

...although wait

[surreal tangle]

Yeah, I was trying to hint at the fact that in nonprime cases you will have 0 divisors

[patent acorn]

ok yeah ny = x always works because...

[patent acorn]

wait ok this was the wrong way round

there are 6 different y values and only 3 different x values

[surreal tangle]

Because only 4 solutions exist for this equation mod 6, (0,0),(0,2) and (3,0) and (3,2). When you plug in other x values(1,2,4 and 5) you won't have integral values for y

For x=1, y=2/3, for x=2, y=4/3, for x=4, y=8/3and for x=5, y=10/3 (y isn't an integer hence the point(x,y) wont correspond to any letter)

[lean hull]

Hello! Let x and y be elements in some field of arbitrary characteristic, and let p and q be distinct prime numbers. Is it true that if x^p = y^q, then x = z^q and y = z^p for some z in the field? I thought this should be false if it's not algebraically closed, but my brain isn't working and I can't construct an example where it fails Sorry I'm dumb but this is obviously true! I know how to prove it now 😛

[oblique swift]

From where came that 36? How it calculated the number of square units?

The book showed only how to find the number of common elements on products of finite intervals but not of infinite interval

[patent acorn]

it's 6 * 6

6 because that's the difference between -1 and 5 (so, 5 - (-1))

[lost yacht]

Proving formulas involving natural numbers by induction, division algorithm, and modular arithmetic then congruences.

[shrewd gust]

I'm having trouble proving the existence of a unique gcd using only the well ordering theorem, the definition of divisibility and Euclidean division (i.e. for $n \in \mathbb{Z}, d \in \mathbb{N}_0$ there exist unique $p \in \mathbb{Z}, r \in \mathbb{N}$ with $0 \leq r < d$ s.t. $n = pd +r$).\

Considering $n,m \in \mathbb{N}_0$, I started by defining
[ d = \max { e \in \mathbb{N}_0 \mid e | n \text{ and } e | m } ]
by the well ordering theorem, and I would now like to show that for arbitrary $e \in \mathbb{N}_0$, $e | n$ and $e | m$ implies $e | d$. Is there an easy proof for this, only using the tools I mentioned? I'm aware this can be done with the division algorithm but I would prefer something less lengthy, and I'm aware this is trivial using prime factorisation but I would like to avoid this in order to avoid circular reasoning.

[sterile pumice]

Yuese

[open mist]

if e doesn't divide d, then write e = ab where a | d, gcd(b, d) = 1
This is provable by letting a = max(n <= e, n | e and n | d} and saying that if b, d have a common divisor c, ac | d contradicts a's maximality
Then argue db | n and db|m:
n = dn' = bn''
b | dn' and gcd(b, d) = 1 so by Euclid's lemma, b | n'
Hence bd | dn' = n

Euclid's lemma can be proven elementarily (cf wikipedia) though it is slightly long

[brittle plinth]

Has a problem similar to this (maybe in generality with Z/n) been studied?

[west glade]

this is called the capset problem

or at least very similar to it

[shrewd gust]

Oof, looks like it's still more complicated than what I was thinking about. But thank you!

[open mist]

There might be simpler. I just invented that proof as a first attempt, so there very likely is shorter