elementary-number-theory

[cobalt hornet]

Hmm but what does p being equal to 1 mod 4 tells us here

[stiff rivet]

nothing

[cobalt hornet]

then why the question is being asked in this way? 🙂

oh i understood

[stiff rivet]

look at (-a)^((p-1)/2) mod p

[cobalt hornet]

yep yep

since p is equal to 1 mod4 we have (-1)^((p-1)/2) = 1

if p is equal to 3 mod4, we have (-1)^((p-1)/2) = -1

[cobalt hornet]

i dont really understand the other argument above, is mine correct?

[stiff rivet]

what

thank

[cobalt hornet]

How one claim from the first one the second equality? and is my calculation correct or the same as above?

[stiff rivet]

idk, probably

plug it into a computer

[cobalt hornet]

its not hard to calculate using the properties of legendre symbol

but idk how they argumented above

[stiff rivet]

yes, im sure you can verify it yourself

i dont see an argument at all

its just a calculation

[cobalt hornet]

how does 45083 = 3 mod5 and 45083 = 3 mod8 imply (2/45083) (5/45083) = (-1)^2

[stiff rivet]

i dont know why you are asking me

i guess you can argue that (2/wtv) = (8/wtv)

then quadratic reciprocity

then i dunno

ask whoever wrote this

[flat scarab]

what is that pfp?

[stiff rivet]

Ziltoid, the Omniscient

you should listen to it

this song has a reference to the proof of fermats last theorem: https://www.youtube.com/watch?v=9cAW900S6HE

[cobalt hornet]

How can i find a characterization of this

$ (\frac{11}{p}) = (\frac{p}{11}) $ whenever $p = 1 mod4$ and $(-\frac{p}{11}) $whenever $p = 3 mod4$

[sterile pumice]

Sentinel

[cobalt hornet]

i think your answer was correct but im having trobule calculating it

[wheat tinsel]

it seems you know quadratic reciprocity then?

[wheat tinsel]

you just have to divide into cases

so if p=1 mod 4, you just have to calculate when (p/11)=1

and for p=3 mod 4, you have to take the non-squares

[cobalt hornet]

hmm i just need to look up one by one to

1+4k and 3+4k until 44 right

[wheat tinsel]

yeah you could do that

[cobalt hornet]

or is there a easier way

[wheat tinsel]

but it is faster to do what I said

you just have to calculate the squares mod 11

[cobalt hornet]

Can you do some? im not so sure about it

[cobalt hornet]

i think the answer should be {1, 5, 7, 9, 17, 19, 25, 35, 37, 43}.

but idk how to calculate it fast

but one still needs to calculate higher numbers right?

[wheat tinsel]

the squares mod 11 are 1^2,2^2,3^3,...,10^2 mod 11

just calculate these numbers mod 11

[cobalt hornet]

we know that p is prime

[cobalt hornet]

idk what u mean exactly by that

[wheat tinsel]

but you only care about its residue mod 11 and 4

[cobalt hornet]

here they calculate one by one (i/11) for i=1, ... ,10

but i dont understand the answers in the right hand side

how do they conclude them directly

[wheat tinsel]

do you know about the Chinese remainder theorem?

[cobalt hornet]

yes

[wheat tinsel]

I'm not sure why you are having problems then. I'm sorry I couldn't help

[cobalt hornet]

For example can you explain the first one just

(2/11) = (-1)^((11^2-1)/8) = -1

its ok

but how do i find p = 35 mod 44 out of it

[wheat tinsel]

I think they are asusming p=1 mod 4. Then (11/p)=(p/11), and (p/11)=1 if and only if there exists an integer x such that x^2=p mod 11. That can happen if and only if p=1,4,9,5,3 mod 11

[cobalt hornet]

so so far so good

so we have several systems to solve with chinese remainder theo or how

for example for the system p=1 mod4 and p= 4 mod11 we have 1+4k = 4 mod11 implies 4k = 3 mod11 implies k = 9 mod 11

so k = 9+11l

and 1+4(9+11l) = 37+44l solves the system

hmmm therefore we have 37 for 4

[cobalt hornet]

But one needs to do it for each system or is there a simpler way?

[wheat tinsel]

yes, you have to solve each congruence

but this is fast, there are just 5 systems in total (and you know the rest of numbers mod 44 are non-residues)

[cobalt hornet]

they dont assume they calculate (i/11) and if its equal to 1 its quadrat and the case p = 1 mod4, if its equal to -1 its the case p=-1 mod 4

[cobalt hornet]

how do i know them mod 44?

i know them for mod 11

so there would be 10 system in my head

[wheat tinsel]

oh well yeah it's 10 if you also include the case p=3 mod 4

but this is very easy

just do what you did, you don't need to write stuff down

[cobalt hornet]

Hmm ok in this way i can do it

but the picture i send you was a little to short for me and i didnt understand the calculation behind it

[cobalt hornet]

thanks a lot

[wheat tinsel]

here is a small table of quadratic residues, from Wikipedia

@cobalt hornet

[cobalt hornet]

@wheat tinsel this is always true right? replacing 11 with q also

[cobalt hornet]

thanks

$ (\frac{q}{p}) = (\frac{p}{q}) $ whenever $p = 1 mod4$ and $(-\frac{p}{11}) $whenever $p = 3 mod4$

so this

[wheat tinsel]

no

[sterile pumice]

Sentinel

[wheat tinsel]

$\Lg{p}{q}=\Lg{q}{p}$ whenever $p\equiv 1\Mod 4$, $p,q$ primes.

[sterile pumice]

croqueta3385

[wheat tinsel]

when $p\equiv 3\Mod 4$ you can only say $\Lg{p}{q}=(-1)^{\frac{q-1}{2}}\Lg{q}{p}$

[sterile pumice]

croqueta3385

[wheat tinsel]

in the case q=11 you get a minus sign

[cobalt hornet]

hmmm okay

i know it with

$(-1)^{(p-1)/2\cdot (q-1)/2)}$

infront of it

[sterile pumice]

Sentinel

[wheat tinsel]

yes

what I said is equivalent

[cobalt hornet]

yep i understood now

thanks again

[wheat tinsel]

(I forgot to say that p,q should be odd primes, but I suppose you are aware already)

[cobalt hornet]

yep

[wheat tinsel]

also note that $-\Lg pq$ is not necessarily the same as $\Lg{-p}{q}$

[cobalt hornet]

odd primes means just not equal to 2 right

[sterile pumice]

croqueta3385

[cobalt hornet]

its a bit funny that one always consider the case p=2 and say it explicitly every time

[tight meadow]

2^(744) mod 10

Any ideas? Euler phi failure

[coral venture]

Try calculating 2^2, 2^3, 2^4, etc. mod 10

You'll see repetition eventually

[charred roost]

you can use the chinese remainder theorem, then euler phi on each factor (or one of the factors, the other one is trivial)

[unkempt void]

Yeah just need to find small k with 2^k = 2

[charred roost]

I used ||2^(4k) = 1 (mod 5)||, then did the normal CRT calculation to conclude that ||2^(4k) = 6 (mod 10)||. Is there a quicker way?

[coral venture]

Knowing ||2^5=32||

[charred roost]

yeah, but how do you go from there to 2^744?

[coral venture]

||Powers of two repeat with period 4. So 2^744=2^4 mod 10.||

You can do it formally with induction if you really want to

[charred roost]

The fact that they ||repeat with period 4|| is the interesting part imo, and the part you have to actually prove. From potato's message it sounded like there was a trick, instead of having to spot the pattern and use induction

Okay, the hint is maybe find a small k different from 1 so you can ||figure out the period||, which I guess makes sense

And I think you can use some group theoretic argument to bypass the induction

[unkempt void]

Well once you know 2^4 = 2 it just is multiplying stuff, like you dont have to spot a pattern

[tight meadow]

Any other method except cyclicity?

I guess we can use binomial expansion?

[tight meadow]

@unkempt void @charred roost @coral venture

[serene sun]

Write $r_k$ to be remainder of dividing $bk$ by $a$.
Suppose $r_{k+T} = r_k + r_T$ for $1 \leq k, k+T \leq a-1$, where $T$ divides $a-1$.
What restriction does this set on $b/a$?

[sterile pumice]

Absta

[serene sun]

Experimentally, this seems to restrict a/b up to 3 continuant terms.

[charred roost]

Well, it's not much of a pattern, but you do have to notice that it repeats with a period of 4. It sounds like you're thinking of it in a different way, can you explain your thought process?

[torn escarp]

yeah since you know it fails because 2=0 mod 2 that means you're effectively working mod 5. So it's really just 2^744 = 2^0 = 1 mod 5 so it really can only be 1 or 6 mod 10 and since it's even it's 6

in general you're gonna have this with odd n working mod 2n

maybe it's a bit too semi specific to really worry about really remembering

[charred roost]

I see, that's basically what I did, except I spent more time going from 2^744=1 mod 5 to 2^744=6 mod 10

[torn escarp]

yeah, I figured as much lol

[charred roost]

but I learned that when you go from mod 2 and mod n to mod 2n, you can just check two values instead of going through the CRT rigamarole, so that's nice to know

[sacred junco]

silly question but if you have something like:

x = 2 (mod 8) then does that imply x = 2 (mod all factors of 8)?

looks like it works cuz it’s reverse crt?

[flat scarab]

whenever someone has a chance, i have this question. there is a little bit of background knowledge required for what they mean by "money order", i tried my best to provide a definition for what the author meant by that, and give the appropriate context, in my solution. let me know if it is still unclear.

here is my solution, it is a bit long-winded. my main concern is the second half of the problem, where we need to prove that an error gets detected, i approached it by cases and was wondering if they were valid. it could be a better problem for #proofs-and-logic , but it does require a little bit of modular arithmetic... appreciate you all, and all the help youve given so far

[still flare]

Mod all factors of 8? Yes. In general if you have x == y (mod ab) then x == y (mod a) and x == y (mod b).

You don't need the CRT to see this, try proving it directly. The CRT is a fairly complex fact, this is much easier to prove.

[leaden stream]

seems reasonable

[flat scarab]

Do you agree or disagree with bounding $a_i$ to the digits 0 through 9?

sorry it’s a long one

[leaden stream]

yeah, thats fine. They're decimal digits

[sacred junco]

not sure if i'm being dumb but does something like this work

x = abq + y and if you divide through by a then you have x/a = abq/a + y/a and so x = y (mod a)?

but this feels off 💀 😭 cuz well that whole definition doesn't require multiplicative inverses, correct?

[silent magnet]

Ok just noticed the #real-complex-analysis channel. Maybe this question is better suited for there

[still flare]

Try again.

[sacred junco]

do i need bezout for this?

[still flare]

No

You need a single set of parentheses.

[sacred junco]

oh lol do i just do x = y (mod ab) -> x = (ab)q + y then let bq be some other integer k so you have x = ak + y implying that x = y (mod a)

and well a similar argument for x = bt + y?

[oblique swift]

How to find numbers with exactly 3 divisors (1 and itself doesn't count) given an interval between n and m ?

Is there a theory to help with that?

[wooden glen]

What would the prime factorization of a number with exactly 3 5 divisors look like?

[oblique swift]

Given like for example 16

It would be 1*2⁴

[wooden glen]

Yes.

But I meant, how do the prime factorization of all numbers with exactl 4 divisors look like?

[oblique swift]

p^4 given that p is the prime number?

[wooden glen]

Yes.

So looking for numbers with exactly 5 divisors (3 nontrivial divisors) between n and m is the same as looking for primes between the fourth roots of n and m.

[oblique swift]

So I just need to keep with p^4 to find all numbers I desire

[oblique swift]

Ic

Thank you

[charred roost]

Yep, or equivalently, x - y is a multiple of ab, and therefore a multiple of a and of b

[still flare]

Yup well done

[sacred junco]

nice thanks guys

[hard plume]

hello
I'd like to find a general formula for k for example for 6k+1 = 0 mod(6n+1) or 6k-1 = 0 mod(6n+1).
Does anybody have an idea?

[nimble scroll]

Guys, I have spent 12 hours on this question and can't figure it out

[torn escarp]

6k+1 = 0 mod 6n+1 means that 6k+1 is a multiple of 6n+1, so 6k+1=(6n+1)m. Now you can reduce this mod 6 and get that 1=m mod 6 so write m=6t+1 and you have 6k+1 = (1+6n)(1+6t) = 1 + 6(n+t)+36nt so you can subtract 1 and divide by 6 to get k = n+t+6nt. So now for any fixed n, you have a free parameter integer t that lets you go through all k.

try to see if you can work out a similar thing for the 6k-1 case

[hard plume]

thank you so much 🙂

[sleek violet]

have you tried strong induction? assume
$\\exists x_0, y_0\in\mathbb{Z}, x_0U_n + y_0V_n = 1 \ \exists x_1, y_1\in\mathbb{Z}, x_1U_{n + 1} + y_1V_{n + 1}=1\\Rightarrow\\exists x_2, y_2\in\mathbb{Z}, x_2U_{n + 2} + y_2V_{n + 2}=1$

[sterile pumice]

esca

[sleek violet]

(the base cases are easy to check)

[nimble scroll]

Yes but it doesn't do anything for me

Or have you solved it?

[rustic tulip]

Can someone give me more idea to this?

I’m aware about the crytographic applications, what specific number theory is used in speeding up numerical calculations?

[hard plume]

we have k = n+t+6nt - is there a simple way to guarantee n<k - such that it's encoded in the equation and not just written on the side? I don't know how to put it but I think you get me

[west glade]

well you can just write t>0 instead next to it

given that you have to write t in Z next to it already, you can combine those to t in N

[hard plume]

i think i need t = 0 for another case

btw i am looking at k, n, t in N only

[hard plume]

@west glade

[west glade]

well then write that on the side

if t>0 then k is automatically bigger than n. because k = n + (something > 0)

[hard plume]

i have another infinite set of solutions in terms of n, k, t and infinitely many within them have t =0. I was asking "way to guarantee n<k - such that it's encoded in the equation and not just written on the side?" whether k>n on the side or t>0 on the side - i would want something st " it's encoded in the equation and not just written on the side"

@west glade

[west glade]

I dont know what original question you are trying to solve but there is no way to exclude k=n if the only equation you have is 6k+-1= 0 mod 6n+1. you will have to change the actual problem you are trying to solve and as we have no idea what that is we cant help you

[torn escarp]

five dollars says this is something to do with trying to prove the twin prime conjecture

[obtuse quartz]

I want to calculate a and n for given k such that
a^k ≡ 1 (mod n)
But
a^(k/2) !≡ 1 (mod n)
Where !≡ is "not congruent under modulo"
And k can always be represented as 2^p with p being natural number (excludes 0)

[torn escarp]

Sounds related to Pollard's rho algorithm, what's the relation

[obtuse quartz]

Never heard of it, what's that?

[gilded breach]

84x - 438y = 156

Determine all the solution to this diophantine equations

[torn escarp]

what have you tried?

[gilded breach]

gcd(84,438) = 6

6 = 84(26) + (-438)5

[torn escarp]

it's a factorization algorithm, might not be directly related to your problem then. You have any other context around this problem since I would expect the solution to be more like a program or algorithm

[gilded breach]

156 = 84(676) +(- 438).130

so x0 = 676 and y0 = 130

But this doesn't match with the answer provided

I'm struggling with how to find the x0 and y0 when it's ax-by = c instead of ax+by = c

In the answer, x0 = 54 and y0=14

[torn escarp]

you can get infinitely many solutions using the fact that x=438 and y=84 make 84x-438y=0

so you can add integer multiples of this to your solution to get a different one

[gilded breach]

I have to see how they got to the other solution

I get confused if I should divide -438 by 84, or just 438 by 84

[ember spire]

this textbook is evil lmao

[torn escarp]

easy version for you: find all triples of primes that differ by 2

[gilded breach]

I think I did this once

[small sable]

2,3,5

Or 5,7,11

[gilded breach]

I don't know if you're joking but they don't differ by 2

[torn escarp]

2,3,5 also don't differ by 2 either

close though lol

[gilded breach]

I meant both of niko's answer, though one was highlighted by discord, because they sent two separate messages.

So the only set is 3, 5, 7

Because in the other sets, at least one of them is divisible by 3

Proof: As we can express any integer as 3n, 3n+1, 3n+2. If the first one is 3n, it's automatically not a prime

If the first prime is 3n+1, then the next integer is (3n+3) which is not a prime

If the first prime is 3n+2, the next integers are (3n+4), (3n+6). 3n+6 is divisible by 3

[sacred junco]

what happens when a = 8 and bc = 8

8|8 is okay but 8|2 is not true?

[still flare]

I don't understand what you're claiming. The statement is:

If x == y (mod ab) then x == y (mod a)
So what counterexample do you claim to have? I see no c in this statement.

[sacred junco]

wait is this claim correct?

a|bc then a|b and a|c?

i think i'm conflating some stuffs

[still flare]

No, but that wasn’t the claim

[sacred junco]

oh yeah 😭 true for some reason i thought uit was related

*it

[still flare]

Glad to have cleared that up

[sacred junco]

can you also tell me the "preconditions" for osmething like

a|bc implies a|b and a|c to hold?

not actually a question but since that came to mind

maybe i should clarify that too

[still flare]

If a is prime this always holds.

This is in fact the definition of a being prime

[sacred junco]

oh makes sense

wait let me think aobut it first

at least that safeguards against my example above i guess

if a = 8 and bc = 8 then it doesn't work so eh a has to be prime

[tacit heart]

How can I show that the multiset ${ij \pmod{89} \vert i \in A, j \in B}$ is ${0,0,1,1,2,2, \cdots, 88,88}$ where $A={-15,-13,-11,-9, \dots, 9, 11, 13, 15}$ and $B={2^1, 2^2, 2^3, \dots, 2^{11}}$?

[sterile pumice]

kappa

[tacit heart]

nvm i got it

[verbal cedar]

i suppose this fits here. suppose $am+c\ell=g=\gcd(a,c)$. is there anything we can say about
$$\frac{bm+d\ell}\mod\frac{ad-bc}{g}$$

[sterile pumice]

inconspicuous old man & mime
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[verbal cedar]

oops

$$(bm+d\ell)\bmod{\frac{ad-bc}{g}}$$

[sterile pumice]

inconspicuous old man & mime

[lilac bronze]

Yes, depends on what you let yourself assume

It’s pretty quick if you assume the fundamental theorem of arithmetic

That every number has a unique prime factorisation

Yes

Hm, if I remember correctly, you wanna prove bezout’s lemma

Then Euclid’s lemma

Existence of prime factorisation is with induction

And then Euclid’s lemma gets you uniqueness

[lilac bronze]

I forget if this is called bezout’s identity or not

[wooden glen]

To a large extent you can copy the usual proof that sqrt(2) is irrational, but just replace "even" with "divisible by p" and so forth.

[lilac bronze]

Mhm yeah

[wooden glen]

Going by FTA leads to a somewhat slicker proof, but it takes more work to reach from a standing start.

[wraith cedar]

namely use the assumption that gcd(a,b)=1 and gcd(a^2,b^2)=1 for a/b

:3

(you can prove gcd(a,b)=1 => gcd(a^2,b^2)=1 from bezouts lemma)

[lilac bronze]

Yeah I think so

[wooden glen]

Yes.

[wraith cedar]

how did you prove square root of 2 was irrational?

this step

you can essentially replace 2 with any prime and it'll still hold

minus the even part obviously

i.e. since a^2 and b^2 don't share any factors (gcd=1), it must be the case that a^2 has a factor of p

well, a,b don't share any factors right

do you agree with that? this is by definition of simplified fraction

so it would make sense for a^2 and b^2 not to share any factors too, as its just the same factors they already have, but multiplied to each other

yes

coprime=gcd of 1

this is where fundamental theorem of arithmetic would help

[charred roost]

You have $pb^2 = a^2$ which implies $p$ divides $a^2$. Since $p$ is prime, $p$ also divides $a$, so we can write $a = kp$ for some $k$. Then we get $pb^2 = (kp)^2 = k^2 p^2 \implies b^2 = k^2 p$, and by the same reasoning $p$ must divide $b$. This is a contradiction, since we assumed $a$ and $b$ to be coprime

[sterile pumice]

sheddow

[charred roost]

substitute a = kp into pb² = a²

Also note that we can use Euclid's lemma to justify the step p divides a² implies p divides a

https://en.wikipedia.org/wiki/Euclid's_lemma

Euclid's lemma is pretty well-known, so it should be enough to just refer to it, unless your professor says otherwise

[crystal agate]

you can prove in general that when c is not an integer root sqrt(c) is irrational

it's a great proof

it was on the ross application actually with a great generalization

just FTA if you go the prime factorization route

if you go down the polynomial route

you only need the rational root theorem

which you probably learned in high school

fundamental theorem of arithmetic - unique factorization in Z

basically the rational root theorem says given a polynomial with integer coefficients, https://en.wikipedia.org/wiki/Rational_root_theorem

just look at the wikipedia

it'll explain better than I can rn ngl

I think it's worthwhile doing yourself

because the proof with polynomials is really really cool

look at the wikipedia page for RRT and see what you can conclude about the roots of monic polynomials

😔

start reading rosen!

[quaint gate]

For now take "$\in Z[X]$" to mean all coefficients $a_i$ are integers

[sterile pumice]

pika

[quaint gate]

you only need unique prime factorization

What part did you not understand

Z[X] is the set of polynomials with integer coefficients

X^n has 1 as its coefficient such polynomias are called monic

[flat scarab]

does anyone know why multiplication (modulo n), is associative? i think it is because the elements being multipled together modulo n, are integers, and integer multiplication is associative. is this right or wrong?

[lilac bronze]

Yes you can deduce it from the associativity of integer multiplication

[flat scarab]

thank you, i know it has to be proven, but i guess when you start unpacking, it boils down to integer multiplication

[lilac bronze]

Mhm, and there are ways to prove that integer multiplication is associative too

[flat scarab]

yeah i am looking at a proof right now

it looks like in the proof, the multiplicative operation (modulo n), is sort of "extracted", and then you are dealing with integer multiplication

i say "extracted", because i cant think of a better way to describe it

maybe "applied" would be better

[lilac bronze]

Extracted is a nice way to think about it

[flat scarab]

basically what i'm trying to say is, you go from $(a \times_{n} b) \times_{n} c$ to $((a \times_{n} b) \times c) \pmod n$

[sterile pumice]

proofman

[flat scarab]

then you repeat this process until you get to the $\bZ$

[sterile pumice]

proofman

[flat scarab]

at which point you can apply associativity

[lilac bronze]

Yes, exactly!

This is essentially because products and quotients commute, for sets

[flat scarab]

so, i'm studying abstract algebra, and then this came up

it really bothered me that i couldn't immediately get the results

but i had a feeling this was it, i just had to think about it

[lilac bronze]

I think partially it’s the notation involved

I find that thinking of it in terms of function notation helps

[flat scarab]

do you ever get that feeling? you are studying an advanced concept, and then something simple comes along and you dont remember how it works?

[lilac bronze]

Actually, I don’t often, but that’s because I’ve taken deliberate steps to avoid this

Namely, making lots and lots of flashcards

[flat scarab]

hmm this is interesting. like for what topics? and how do you go about making the flashcards?

[lilac bronze]

Well, I used flashcards for essentially my entire math degree

[flat scarab]

im trying to think, how would a math flashcard work?

[lilac bronze]

The software I use is Anki

[flat scarab]

i remember flashcards for studying foreign language only

[lilac bronze]

It’s fairly straightforward to make flashcards for things like definitions and theorem statements

I also often make them for proofs or longer explanations

[flat scarab]

thats interesting, why did you do this? just to remember? or to pass an exam?

[lilac bronze]

To remember, and to help me understand them

It also helped greatly for exams

[flat scarab]

when i had exams, i would do all problems again maybe 2-3 times until i could do them all without notes

[lilac bronze]

Yeah, I would do practice problems too

[paper lion]

Can one sidestep the prime number theorem to prove that the upper density of primes in N is 0?

Specifically, I would like to know if the presence of arbitrarily large gaps between primes can be leveraged to prove that

[sacred junco]

This is certainly not enough on its own

You can have a set with arbitrary large gaps but nonzero upper density

[flat scarab]

quick question: suppose that $p$ and $q$ are distinct primes... is it reasonable to say the following:
since $p$ is prime, $p + q$ does not divide $p$, and since $q$ is prime, $p + q$ does not divide $q$. thus, $p + q$ does not divide $pq$

[sterile pumice]

proofman

[flat scarab]

to me, this looks like the contrapositive of Euclid's Lemma

[sacred junco]

Did you mean to say p does not divide p+q, and similarly for every other instance of divide?

[flat scarab]

No actually this follows from another larger problem i am working on, but i am focused on the number theory aspect

[torn escarp]

it doesn't make sense, since p+q is larger than p or q and will never divide them

[sacred junco]

If you allow integer primes, p=-2, q=3 is a counterexample but you probably don't mean that, else ^

[torn escarp]

a|b means a<=b

(for positive integers)

[flat scarab]

Ok, that all makes sense

The author states that $\gcd (p + q, pq) = 1$

[sterile pumice]

proofman

[flat scarab]

that was my guess as to what the reason was, but I missed a very obvious thing, p + q > p and q

[torn escarp]

that sounds sketchy

[flat scarab]

can you elaborate?

[torn escarp]

p+q > p and q isn't enough to prove gcd(p+q,pq)=1

[flat scarab]

here is the FULL problem (if anyone is interested), and my attempted solution (which is wrong), i've already started working on a new solution, so you can just ignore that one
#groups-rings-fields message

[torn escarp]

gotcha

[flat scarab]

oh no, that wasn't the whole thing

[flat scarab]

there's more to it that i purposely left out

[torn escarp]

yeah then you're good if you're still working at it, I thought you meant that was "it" haha

[flat scarab]

no no no

so what we have are that $p$ and $q$ are distinct primes

[sterile pumice]

proofman

[flat scarab]

somehow, the author concludes from this fact, that $\gcd (p + q, pq) = 1$... how is that possible?

[sterile pumice]

proofman

[torn escarp]

way I see it is the only factors of pq are 1, p, q, and pq so we can focus on just p or q as dividing the gcd, so p or q would have to divide p+q

now since p|a and p|b implies p|(a+b) I take a=-p and b=p+q and have p|q which is a contradiction since they're distinct primes

[flat scarab]

can i just say:
suppose $\gcd (p + q, pq) > 1$, then $p$ divides $p$ and $p$ divides $q$, we have reached a contradiction since $p$ and $q$ are distinct primes?

[sterile pumice]

proofman

[torn escarp]

how do you say p divides q though

[flat scarab]

i think im messing something up

this is not quite what i mean

if $\gcd (p + q, pq) > 1$, then without loss of generality, either $p$ or $q$ must divide $p + q$...

[sterile pumice]

proofman

[flat scarab]

@torn escarp does the above make slightly more sense?

because $p$ or $q$ would have to be factors of $p + q$ in order to have a $\gcd > 1$

[sterile pumice]

proofman

[torn escarp]

sure, but what if I tell you you're wrong and p divides p+q?

[flat scarab]

im not too sure that's possible

[torn escarp]

yeah, you need some kind of lemma or theorem to appeal to in order to assert that p can't divide p+q

[flat scarab]

I think p would have to be able to divide p and q for that to be true

[torn escarp]

that sounds reasonable, but I don't consider that to be proof

a similar sounding reasonable argument is 2 doesn't divide 3 or 5 so 2 doesn't divide 3+5 maybe

[flat scarab]

So basically what you are saying is that I need to look up what lemma this is?

[torn escarp]

well just this, I don't know if it has a name

[flat scarab]

This is just not clicking for me, my brain might be fried

[flat scarab]

This was funny by the way

I laughed a little bit

[torn escarp]

I think I said it a bit tersely too, I can expand it out a bit

basically we would like p | p+q, so let's suppose it's true. Then because p| -p we have that p divides their sum, p | (-p + p+q) which is the same as p | q. This is false because p and q are distinct primes and primes by definition are only divisible by themselves and 1. So we just derived a contradiction, so our original assumption was false, so p does not divide p+q

[flat scarab]

Ok this makes sense, and then without loss of generality can we extend to q does not divide p + q?

[torn escarp]

yeah, p and q are symmetrical in how they appear so you're right, argument works wlog and you're done

[flat scarab]

Cool, still kicking myself for not getting that right away

[flat scarab]

i did another similar one on my own, wondering if someone can take a look... suppose p and q are distinct primes: @torn escarp

[west glade]

p^2 is also a factor of p^q

[flat scarab]

If I leave out the comment about the factors, does this proof work?

[west glade]

well why does p have to divide q^p. you still have to argue that

[flat scarab]

I guess I should say something more like, some factor of p^q must divide q^p instead, and then the only factors of p^q are powers of p, does something like that work?

[west glade]

depends on how you word the "something like that"

[flat scarab]

If a power of p were to divide q^p, then so would p?

Since p is a factor of p^n for some n

[west glade]

yes

[flat scarab]

Ok, so put everything together and it works?

[west glade]

the euclid lemma step of course depends on the version of euclids lemma you are using. but imo its fine enough

[flat scarab]

You mean like extended application versus just regular euclids lemma (the p divides ab )?

[west glade]

yes

if you just have the regular one you would need to apply it a few times to get down to p|q

[flat scarab]

Got it, thank you for taking your time to look at this, I do appreciate it

[west glade]

yw

[paper lion]

[raven kayak]

Hi, I have a doubt in this sentence. Why if the average order of f(n) is a constant (in this case log2), this implies that f(n)=0 infinitely often??

[sacred junco]

What is the codomain of f?

Is it natural number valued?

Also how do they define average value?

[raven kayak]

f(n) denotes the number of representations of n as the sum of one or more primes

consecutive primes

[sacred junco]

Okay, so it is natural number valued

[raven kayak]

yers

yes

[sacred junco]

How do they define average value of a function from N to N?

Limit of averages on finite initial segments?

In any case, this ought to boil down to the fact that 0<log(2)<1

[raven kayak]

is the limit of $\frac{1}{x}\sum_{i=1}^{x}f(n)$

[sterile pumice]

abcdef

[sacred junco]

Makes sense

[raven kayak]

n=1 sorry

[sacred junco]

Suppose the f was not 0 infinitely many times

Then there is an n_0 such that f(n)>=1 for all n>n_0, right?

[raven kayak]

right

[sacred junco]

So your partial sums will become

Bounded below by $\frac 1 n \sum_{k = n_0}^n 1$

[sterile pumice]

Bequi

[sacred junco]

Which is equal to $\frac {n-n_0} n$

[sterile pumice]

Bequi

[sacred junco]

What is the limit of this as n->oo?

[raven kayak]

1

[sacred junco]

So your limit is bounded below by 1

Which contradicts it being log(2)

[raven kayak]

thank you

so this happens when the average value is just a constant not depending by x

[surreal tangle]

Well the average value of a function over N (by your definition) will always either be a constant or not exist

[surreal tangle]

f(n)=0 infinitely often happens because of this in this case

[raven kayak]

for example, the average value of the couting divisor function $\tau(n)$ is log n

[sterile pumice]

abcdef

[surreal tangle]

Okay 2 things:\newline

1. im not sure if thats true \newline
2. im talking about the average value over $\mathbb{N}$. I.e $$\lim_{N \to \infty}\left(\frac{1}{N}\sum_{k=1}^{N}f(k)\right)$$

[sterile pumice]

quicdoom

[keen pagoda]

if I have a polynomial f in Z\Zp[x] and f(x) is a quadratic residue for every x, does that mean the polynomial is another polynomial squared?

[torn escarp]

what does Z\Zp[x] mean, I'm guessing you mean Z/pZ[x]? I suppose we need p != 2 too. Do you consider 0 to be a quadratic residue?

oh x^p-x =0 mod p and 1 is a QR so x^p - x + 1 is not even degree so isn't a square

I guess that's actually an artin schreier polynomial too, funny

[keen pagoda]

Yeah I forgot the notation

And I'm not considering It a qr right now

[keen pagoda]

Cool, thx

[torn escarp]

I think we can extend this result in a handful of fun ways too

like g(x) in the ideal (x^q-x) of F_q and a in F_q we'd have f(x)=g(x)-a always irreducible and of arbitrary degree so we can reason that it can be for any q or any power

so like instead of showing the squared case, we want to show the nth power case, pick a to be an nth power, then pick say, g(x) to be of degree qn+1 (just multiply x^q-x by x until the degree is good) and then we have a counterexample

[keen pagoda]

idk what an ideal is ;-;

some day I'll learn algebraic nt

[torn escarp]

sorry that's on me for loading up on jargon, for our case here it just means all multiples of x^q-x like x^3*(x^q-x)

[keen pagoda]

oh yeah

I do wonder when I have the specific case of a polynomial of degree less than p-1

[torn escarp]

we might be able to work those out by a counting argument one way or the other

[keen pagoda]

like cus if I can build a polynomial that achieves all the square roots and it's also degree less than p than I guess they will need to be the same cus the difference polynomial would need to have too many roots?

I mean, the square will be the same as the other

idk if I really want to solve this rn I was asking cus that idea would be extremely convenient for a specific problem I'm doing

[torn escarp]

I will say that's originally how I came across this, I was thinking that constants don't satisfy the condition, how could I turn them into ones that don't, so I added on 0 in the fancy say x^p-x

since 0 is not a QR, it means we necessarily must use irreducible polynomials

or wait I think I have that backwards nevermind

0 isn't a QR so it's not a problem, if it were then we'd have issues I think

I'm just waking up lol

[keen pagoda]

happens

time zones are amazing cus I'm already in a tired afternoon and you're just waking up

[torn escarp]

well I woke up 2 hours ago heh...

this is part of my weekend for my work schedule

[keen pagoda]

oh

that seems nice

[torn escarp]

I work evenings too so I wake up later yeah, very comfy

[keen pagoda]

unless you have to work in normal weekends too than that'd be very unnice

[torn escarp]

I work four 10 hr shifts, so I have Sun, Mon, Tues off

[keen pagoda]

cool

[torn escarp]

trying to lay out a counting argument to see if it works or not just going to post what I have so far since it's getting a bit bloated

There are ((p-1)/2)^p functions from Z/pZ to (Z/pZ*)^2
There are p^(p-2) polynomials of degree at most p-2
When we look at square polynomials of degree less than p-2, they must be at most degree p-3, so a square root would be degree n <= (p-3)/2.
There are p^((p-3)/2) polynomials of degree at most (p-3)/2 and since 0=-0 if we remove that, the rest break into two groups of +f(x) and -f(x) that square to make f(x)^2, so we have exactly
(p^((p-3)/2) + 1)/2 polynomials that square and remain degree <p-1

there's a slight mismatch to be fixed up since the number of functions from Z/pZ to Z/pZ is p^p which is a bijection with the number of polynomials of degree p-1, but since we're looking at degree p-2 we are throwing out the "almost constant" term x^{p-1}

I say almost constant because x^{p-1} = 1 for all values except 0 which is 0. In fact using that of the form k(x)=1-x^{p-1} gives us a function that's k(0)=1 and k(x)=0 for x != 1 so you can shift this around to prove the bijection

like lagrange interpolation if you've seen that before

[keen pagoda]

damn

[tough condor]

How can I show $|4^{3^n}-1|_3\downarrow 0$?

[sterile pumice]

nHail

[tough condor]

This is part of showing that 2^3^n converges in Q_3

[torn escarp]

euler's theorem will get it for you in this case

[tough condor]

Oh I see it now

Nice, that is clean

[torn escarp]

and you can use induction a bit more generally if you want to show a^{p^n} - w goes to 0 for w being a pth root of unity in Q_p and a having the same residue mod p

[tough condor]

I should have recognized 2*3^n as the totient

[torn escarp]

yeah, also another trick is you could've used the lifting the exponent lemma if you happened to hear of that, not as common maybe

[tough condor]

Looks like I need to review more ENT lemmas and such

[torn escarp]

yeah maybe a bit, personally I wouldn't stress too much, you'll sorta naturally get a better understanding of them as you get into p-adics I feel too and review as is necessary

[lament gyro]

Anyone got any ideas on how to determine if a natural number, n, can be expressed as a unique sum of positive powers of a positive integer k. For example if n =3 and k = 2, 3 = 2^0 + 2^1. Or if n = 11 and k = 10, so 11 = 10^0 + 10^1.

was wondering if there was a theorem or algorithm I could use.

If k is prime, that's easy. we can just use modular arithmetic i think, but the general case may not be as easy.

[lament gyro]

actually that's not true

[torn escarp]

should be true, another way to phrase this is you're proving that the base k expansion of a natural number is unique

[fading void]

hey can someone explain to me how the highlighted section works here?

I agree with everything up until that point, but I'm unable to see how they conclude.

[lament gyro]

Sure. But not every number will have that base k expansion.

So for context, I need to determine if a number, n, can expressed by $n = \sum_{i \in S} k^{i}$ for some $j \in \mathbb{Z}_{>0}$ where $S \subset \mathbb{N}$

I need to code this, so I cna use loops and stuff. But I'm trying to find a way of doing this efficiently.

or even if anyone knows what the name of this number is that would be helpful

[torn escarp]

I see, then you can check if n % k == 1 or 0, then do floored division like n //= k and continue until you either get something not 0 or 1 or n becomes 0 and you're done

[sterile pumice]

theaveragejoe6029

[lament gyro]

oh yeah. Good idea

[fading void]

why does the uniqueness of prime factorization imply this?

[leaden stream]

they're just trying to point out that because it's a multiple of (p-1)p^(k-1) and divides (p-1)p^k, and those two things differ by a single prime factor, that the it must be one of those two numbers.

[feral olive]

On rsa, as 1^e mod 65537 =1, is it possible to recover the full message from the 1 or only the 1? I admit the message has no padding.

Please?

[charred roost]

do you mean the ciphertext is 1? then the message is 1 also

[feral olive]

Yes

[feral olive]

If i know an element, can i uncipher all?

Oh i just read

Also we know for RSA that it has homomorphic property of multiplication.That means when a encrypted text is multiplied with another encrypted text , decryption of resulting value will yield something meaningful.

[feral olive]

I was just curious

[west glade]

!elliptic curve meme

[rotund gust]

🍎 = 154476802108746166441951315019919837485664325669565431700026634898253202035277999
🍌 = 36875131794129999827197811565225474825492979968971970996283137471637224634055579
🍍 = 4373612677928697257861252602371390152816537558161613618621437993378423467772036

[gleaming geode]

Oh, I didn't realize this got posted that often lol

Sorry about that

[charred roost]

In this proof of the fundamental theorem of arithmetic, is the "base case" n = 2 even needed? I would argue that every prime is a base case, since it's basically well-founded induction over the naturals with the divisibility relation. The case n = 2 is already established by the sentence "if n is prime, there is nothing to prove". But some people on wikipedia don't agree...

https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic#Existence

[feral olive]

Hello. I would like to proove these 3 statements.

A)
Theorem: if a I b and b I c then a I c

Proof:
a divides b then b = a * x
b divides c thrn c = b * x

a \in b and b \in c -> a \in c

Then a divides c.

Is ot correct please?

[urban narwhal]

Is 'a \in b' a typo? Also, b=ax and c=bx is not generally true, you should introduce a new variable for each. So b=ax and c=by.

[lilac bronze]

What’s x here

[urban narwhal]

Sorry didnt mean to add that after you sent i was already editing my message >,<

[feral olive]

Wrong channel sorry

[barren dock]

THIS IS A COMMAND BUILT INTO THE BOT?????

who wrote a command that prints out the answer to a random shitpost on command

[tough condor]

The shitpost is common enough that we have a response to it

[crystal agate]

I mean, it’s good practice. Really, for most proofs by strong induction, a base case is not needed (since the claim is vacuously true, as it is here)

But a base case is a sanity check

[keen pagoda]

I generally try like 3 base cases just to be completly sure

like n = 0 n = 1 are a must and then I just try n = 2 just in case

[charred roost]

Yeah, but a sanity check is just something you do for yourself, as part of the discovery process. I'm not saying the base case n = 2 is unnecessary because it is trivial, I'm saying that when you do strong induction of the form (forall k∈ℕ, k < n => P(k)) => P(n), the base case is simply not needed, because < is a well-founded relation

[leaden stream]

Generally you want to show a base case so you can demonstrate that this induction is actually useful and valid. If you just assume it's true for k<n, without demonstrating that it actually true for some value, then it may not actually work for any thing (this implication holds on an empty set isn't often helpful). Going with the typical 'induction ladder' explanation: you should show you can actually get on the ladder, otherwise climbing it is irrelevant.
Sometimes that means you include a silly sentence like 'Look, 2 is prime.'

Example where induction without base case fails: n^2 + 5n + 1 is an even integer for all positive integers n. This can be proved with induction on n (without a base case). It's also never true and always odd.

[charred roost]

But this precise form of strong induction does not need a base case (or rather, the base case is built into the inductive hypothesis) because < is a well founded relation. If you prove (forall k∈ℕ, k < n => P(k)) => P(n), then this implication need to hold for 0 in particular, in which case the premise is empty, and you're forced to prove P(0).

It's possible to reformulate the proof of FTA in a way that makes it more apparent that the base case is not needed: assume for sake of contradiction that there exist some numbers that cannot be written as a product of primes. Let n be the smallest such number. If n is prime, then we have a contradiction immediately. Otherwise n = ab for some a, b strictly between 1 and n. Since n is the smallest number that cannot be written as the product of primes, a and b can be written as the product of primes. But then we can write n as the product of primes since n = ab, so we get a contradiction. This is basically the same as the strong induction proof, but using the well-foundedness of < explicitly

[leaden stream]

you've reformulated your induction proof into a proof by contradiction. Which I agree, does not need a base case.

[charred roost]

I think people are understandably hesitant to leave out the base case, and it doesn't hurt to include it. But it's just a bit redundant to say, first P(2) is true because 2 is prime, secondly P(n) is true when n is prime

[small sable]

Does there exist some work on wether every even number can be represented as a difference of two primes. Is there some work on this

[rustic tulip]

Is there any way to quickly find largest prime factor of a number?

[sacred junco]

This is an open question https://t5k.org/notes/conjectures/

[sacred junco]

There isn't a known quick way to do that

[rustic tulip]

What’s the known efficent way?

[sacred junco]

General number field sieve, I believe

[sacred junco]

It is worth noting that many currently used forms of cryptography rely on people not having an efficient way to do this

[rustic tulip]

I’m trying to do a project euler problem

This number is the 600851475143

I tried to do a naive approach, ie obtained the list of all the prime factors and find the max of the list

[rustic tulip]

But it’s remarkably slow with this number

[stiff rivet]

this is only 40 bits

shouldnt take too long to factor it

but in general this problem is very hard unless your number has a special structure

,w factor 600851475143

[sterile pumice]

Results provided by WolframAlpha

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

Requested by lochverstaerker

[rustic tulip]

How does wolfram factor it?

[stiff rivet]

we dont know

[rustic tulip]

Let me show you my situtation

just a min

[stiff rivet]

probably pollards rho algorithm though

[rustic tulip]

You can see the cell is still running [* ]

I’m guessing my code should be very inefficent here

[stiff rivet]

yes

[rustic tulip]

Has a runtime > O(n)

I suppose

[stiff rivet]

depends on your model of computation

but probably no

it does O(n) many trial divisions

where n is the input number

[rustic tulip]

for each i, it looks for i^2, i^3,…

[stiff rivet]

but the input number has O(2^n) bits

[rustic tulip]

I mean, if its divisible by 2, it will look for 4, then 8, so on until no factors are there

[stiff rivet]

sure but the n = n/i then decreases the number logarithmically

[rustic tulip]

oh

Can I do it in O(sqrt(n))?

[stiff rivet]

yes

[rustic tulip]

minor changes?

[stiff rivet]

dunno if that will help much

your number has 40 bits

even if you do the obvious changes

[rustic tulip]

I can find the smallest prime with in O(sqrt(n)) but not sure the larger one

[stiff rivet]

you only need to check up to sqrt(n)

if you dont find a divisor up to that range, your number is prime

so if you "divide out" all primes up to sqrt(n), what you are left with is either 1 or a prime number

you can also alter the for loop to make 2 steps in every iteration

really checking the even numbers isnt worth

as there is only 1 even prime number which you can check in the beginning

[rustic tulip]

Consider this case n= 600851475143

,w calc sqrt( 600851475143)

[sterile pumice]

Results provided by WolframAlpha

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

Requested by dotdoc.

[rustic tulip]

The bound is too big

All the prime factors are below it

[stiff rivet]

eh

its probably fine

,w 775146 ms in minutes

[sterile pumice]

Results provided by WolframAlpha

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

Requested by lochverstaerker

[stiff rivet]

the modulo operator (on fixed word size inputs) is constant time

but suffice it to say that wolframalpha uses a better algorithm lol

[rustic tulip]

yes

Oh, it gave me an answer in the bash mode

It still doing something though

I think the resources could be limited for web mode.

I’ll try to do in sqrt(n)

[charred roost]

The for loop runs all the way up to n. The fact that you divide n by i in the loop body does not affect the for loop, which is why it takes so long

Your approach is fine for this number, since the prime factors are tiny

[barren rampart]

Is this even true
For all primes p, there exist naturals a and b such that
a²+b²+p and a²+b²+2p both are perfect squares?
If not
Whats the thing similar to it which is true

[chrome oar]

minimum Difference between squares = 2n + 1

2 is prime.

Therefore, there exists no form with the prime 2 that you described, as it is too small to be the difference between squares, as 0->1 = 1, 1->2 = 3, 2->3= 5, etc. (2n+1)

so for the prime 3, 4 needs to be 2p, and 1 needs to be 1p+a^2... etc. but 4 is smaller than 2p, ignoring all the other stuff. So 3 also fails?

Pretty sure the entire thing is bogus

[hot cipher]

What the f is the commutator group?

I had that on my exam today and i didnt understand what it was

[still flare]

The subgroup generated by commutators

Commutators are elements of the form aba^-1b^-1

[sterile pumice]

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

[obtuse quartz]

I want to find a (not necessarily a smallest) primitive root of a prime number.
And the wikipedia page suggests there is no direct formula, hence I need to try and check.
And to get a primitive root of n, I need eulers totient function of n, and its prime factors.
Since it's a prime, the totient function part is easy, but prime factor will be difficult.
Is there an algorithm to find prime factors of approximately 1000 bit number?

[patent acorn]

nobody has factored the 862-bit number 22,112,825,529,529,666,435,281,085,255,026,230,927,612,089,502,470,015,394,413,748,319,128,822,941,402,001,986,512,729,726,569,746,599,085,900,330,031,400,051,170,742,204,560,859,276,357,953,757,185,954,298,838,958,709,229,238,491,006,703,034,124,620,545,784,566,413,664,540,684,214,361,293,017,694,020,846,391,065,875,914,794,251,435,144,458,199 yet, so in general no

but if it's a number that you found mostly at random, instead of a number constructed to be difficult to factor like this one (which has exactly two prime factors and they are both massive), then you probably have a better chance of finding at least some of the factors

[past spire]

Can we have an order of natural numbers that will be equal to any infinite countable ordinal?

[sacred junco]

Of course

By equal I assume you mean isomorphic

[past spire]

Yes

[past spire]

I've heared that you can't on quora, but it's probably quora, and it seemed weird so I've asked.

Also why does it work like that?

capital omega is first uncountable ordinal

[sacred junco]

What is phi?

[obtuse quartz]

It's not constructed to be difficult to factor.
For example simple brute force of 2 <= d < 2^16 did find some factors.
Or pollard rho algorithm managed to find 3 relatively large divisors. (Say, around 32bits)
Also it's in a form of 2^x - 1 (mersenne number but it's not a prime) - ignoring trailing zeros in binary since that's an easy factor, 2.

[charred roost]

The special number field sieve is apparently efficient at factor mersenne numbers: https://en.wikipedia.org/wiki/Special_number_field_sieve

[obtuse quartz]

Interesting!! Ty

[tranquil shoal]

uh this is not what phi is btw

or

more accurately

its a restricition of phi

the full function phi is a binary function (in the arity sense)

https://en.wikipedia.org/wiki/Large_countable_ordinal#Predicative_definitions_and_the_Veblen_hierarchy
this is the full definition

[past spire]

it's from cantor's attic
https://neugierde.github.io/cantors-attic/Lower_attic

[tranquil shoal]

basically has $\varphi(0,\beta)=\omega^\beta$;\
$\forall \alpha[\varphi(s(\alpha),\beta)]$ is the $\beta$-th ordinal (lets call it $\kappa$) such that $\varphi(\alpha,\kappa)=\kappa$

[sterile pumice]

!Pymamba™

[tranquil shoal]

oh does seem like varphi function is different from psi

[past spire]

Also what does computable mean in simple words?

I mean how to easly describe it

Is this possible

[tranquil shoal]

id just have to say smth like 'able to do XYZ within a finite number of steps'

without any new techniques or idea all of it has to come purely from an algorithm

[past spire]

k

So in the case of Church–Kleene ordinal it means that we can't construct any order of natural numbers isomorphic to the ordinal?

[tranquil shoal]

uh thats beyond me lmao

youd have to ask someone in #foundations probably?

this whole convo seems more appropriate there so lets shift towards there

[past spire]

Sorry Im just a kid asking stuff, so I don't understand a lot lol

[past spire]

no access

[tranquil shoal]

go to #info

from there theres a button to give your self the role

[tranquil shoal]

also theres no problem with that lmao

[distant monolith]

Show that, If p is an odd prime, then there exist integers a, b, k such that a²+b²+1=kp and 0<k<p.

[sacred junco]

I believe this will be equivalent to whether -1 is a sum of two squares mod p

Are you familiar with modular arithmetic?

[dreamy agate]

Hi, I'm taking number theory this year but I find it really difficult

Does anyone have any suggestions on how I should study it?

[crystal agate]

What do you find difficult?

Proofs? Computations?

Or concepts?

[dreamy agate]

Proofs

[crystal agate]

Maybe try studying something like Hammond’s book of proof and just getting practice with basic proofs

It’s kind of a unhelpful response ik

But the way to get comfortable with proofs is to do a lot of them

[distant monolith]

Yes

[sacred junco]

Consider the function x² from Z/pZ to itself. Can you find the exact size of the image of this function?

[dreamy agate]

Ok, thank you!

Our teacher doesn’t really teach us how to do it though, he just gives us a really easy example and lets us do a really hard one for homework

And doesn’t even expect us to get it 😭

[crystal agate]

If you do enough practice, then you’ll get it when he doesn’t expect you to :))

[dreamy agate]

Thanks

[mellow ermine]

This is a programming related question, related to something I'm trying to implement.

I want to perform modular exponentiation of arbitrary precision integers. I have arbitrary precision multiplication & addition available, however the modulo/remainder operator "%" is limited to 512 bit arguments.

The algorithm I have is:

function modular_exponentiation(base, exponent, modulus):
    result = 1
    base = base % modulus
    while exponent > 0:
        if (exponent % 2 == 1):  # If the current bit is 1
            result = (result * base) % modulus
        exponent = exponent >> 1  # Shift right to process the next bit
        base = (base * base) % modulus
    return result

There must be some properties of modulo arithmetic that can be leveraged here. I know it's possible because RSA verification libraries exist which do this calculation with arbitrary bit length arguments. Can someone please help me? Thanks 🙂

I worked out an algorithm for arbitrary precision multiplication, by partitioning the input and carrying over the result with Dynamic Programming going from right to left in groups of 64 bytes (512 bits). This seems way harder though!

[mellow ermine]

I think i have something figured out

Using Barrett Reduction

https://en.wikipedia.org/wiki/Barrett_reduction
So TLDR: the remainder can be calculated with multiplication instead of division, allowing my arbitrary precision multiplication function to be used to compute a mod b for a & b of any size

[fossil fog]

This is something that I haven't really thought about much in a long time, but if we create a bijection between $\mathbb{N}$ and $\mathbb{Z}^2$, we can then make a surjection from $\mathbb{Z}^2$ onto $\mathbb{Q}$ which is not injective.\
So you can have surjective mappings which aren't bijective between sets with infinite cardinalities; this is why to show countability we just need to show that there exists \textit{some} bijection between $\mathbb{N}$ and the set.\
This also shows a key difference between finite and infinite sets since finite sets have that they are surjective if and only if they are injective. (I most definitely learned this at one point, but I just haven't thought about it in a while.)

[sterile pumice]

JJCUBER

[fossil fog]

And I guess another obvious example would be to map $\mathbb{Z}^2$ onto $\mathbb{Z}$ with $f(a,b) = a$

[sterile pumice]

JJCUBER

[sacred junco]

f:{0,1}->{0} given by f(x)=0 is surjective but not injective

[fossil fog]

Ah wait I think I was talking about finite sets with the same cardinality at the end🤦‍♂️

[sacred junco]

Then it's true

[feral olive]

Hello. I would like to find a and b in 16261 ×a + 85652 × b = 161.

What did i do wrong please?

[covert forum]

The answer will be in negative

[feral olive]

Is 53 and 10 good like 53×16261-10×8562?

[feral olive]

Because it is currently wrong

[forest plank]

If you know their gcd you can first divide them by the gcd to make the calculations mich easier

[feral olive]

I am confused. Are 53 and 10 correct please?

[charred roost]

do a = 53 and b = 10 satisfy 16261a + 85652b = 161?

[feral olive]

No but in another order is it correct?

[charred roost]

what do you mean by another order?

a = 10 and b = 53? Try it and see

,rotate

[sterile pumice]

Couldn't find an attached image in the last 10 messages.

Sep 4, 2024, 2:40 PM

[charred roost]

,rotate

[sterile pumice]

Couldn't find an attached image in the last 10 messages.

Sep 4, 2024, 2:40 PM

[feral olive]

Non of them provide 161

[feral olive]

Could you just tell me what is wrong please?

[charred roost]

You likely made an arithmetic error

[feral olive]

Very interesting but where?

[charred roost]

dunno

are you using a calculator?

By the way, if you accept negative remainders you can save a few steps. Instead of writing 16261 = 4347 * 3 + 3220, you can write 16261 = 4347 * 4 - 1127. Reducing the absolute value of the remainder leads to fewer steps, and less chance of making a mistake

[feral olive]

Yes

[feral olive]

Can i focus on my method?

[feral olive]

Did this error occures before or after i get 10 and 53?

Hello. I would like to get the values a and b in a 16261 + B 85652 = GCD(16261, 85652 ) = 161 how can I do please?

[charred roost]

You checked that 10 and 53 is incorrect, so clearly before

[charred roost]

What I described is your method, except changing one coefficient by 1

[feral olive]

thanks

I imagine the root issue is in the array

as the result 161 is good!

[feral olive]

is the issue on the array or on the GCD please?

[charred roost]

,rotate

[charred roost]

The gcd is correct, gcd(16261, 85652) = 161. I'm not familiar with the array method, sorry

[small sable]

Could someone clarify what epsilon is please, is this a definition for it ∀x ∈ ℝ , x > ϵ ∧ ϵ > 0

Thanks

[small sable]

That looks Euclidean-y

[slim parrot]

Can we try to prove the theorem, that there are infinitely many primes of the form $4q+3$ other than the usual method of thinking about a number $4q_1q_2 \dots q_n -1$ where all $q_i$ are the finitely listed primes of form $4q+3$.
Like trying to think of some other number which is of some different form, say what if you start from $q_1q_2 \dots q_n +2$ or so on.
Sure we prefer to have +/- 1 which makes it easier for us, but can we in any case prove by taking a number like this?

[sterile pumice]

NightBaron

[vernal dome]

Revisiting some stuff I haven't looked at in a long time; I wonder, in this definition, do they
a) demand that a_k is nonzero only for a finite number of negative indices k for the sum to converge?
b) why require a_k\neq B-1 for an infinite number of positive indices k?

[west glade]

the negative indices are the "digits" before the decimal. there should only be finitely many of those

the not B-1 condition rules out things like 0.99999999999...

[vernal dome]

ah ok, thanks 🙂 so in a proper expansion, the representation is unique?

[west glade]

yes

[small sable]

I think you can prove it in a way with mods, like think of the scenario when q is even, then you prove that 4q + 3 is -1 mod(6), and this is a known result that there are infinitely many primes of this form

[stiff rivet]

dirichlets theorem proves there are infinitely many primes in any arithmetic progression (unless it's trivially impossible)

the statement is proved by analytic means

essentially by considering the sum 1/p in the set over all primes and showing it diverges

[small sable]

Wait how does that sum prove that statement, kinda curious

[stiff rivet]

a finite sum can't diverge

[small sable]

Yea, primes are infinite

[stiff rivet]

its a sum over the primes of the required form

i.e. in the arithmetic progression

[stiff rivet]

well, their reciprocals

[small sable]

But if you do that from the on-go, arent you automatically assuming that there are infinitely many primes of that form

[stiff rivet]

no

[small sable]

How

[stiff rivet]

i could ask you the same

considering some sum doesn't imply its infinite

i dont understand what you mean

[small sable]

I dont get your question, could you elaborate

[stiff rivet]

what question 😵‍💫

[small sable]

This

[stiff rivet]

how does that assume infinitely many primes of that form

if you sum the reciprocals of all the primes of that form

[small sable]

But implying there are infinitely many p of that form does indeed imply there are infinite p of that form

[stiff rivet]

there is no such implication

[small sable]

Yea there is

[stiff rivet]

you just sum them and notice it diverges

[small sable]

Like summing 1/(an+b)

[stiff rivet]

you have some sum of the form $\sum_{p}\chi(p)1/p$

[sterile pumice]

Lochverstärker

[stiff rivet]

where chi is zero if its not of the required form

and go over all primes

chi is like an indicator function of the arithmetic progression

[small sable]

Isnt that just a mathematical representation of the statement, like i dont think its possible to prove infinitude just from that

[stiff rivet]

it is

just show it diverges

if there are only finitely many primes of the form, this sum is finite...

the contrapositive proves the statement

[small sable]

Yea, but then you are back to like automation or in the bare case a sum over all prime reciprocals

[stiff rivet]

no

0*anything is zero

[small sable]

Yea ik

[small sable]

Like how would you show it diverges from that sum, sorry if its a dumb question

[stiff rivet]

yes, thats hard

[small sable]

Impossible*?

[stiff rivet]

its a complex argument and requires a lot of complex analysis

its called dirichlets theorem on arithmetic progressions

there is an associated function called an L function

defined on the complex plane except some pole

and studying behavior at this pole gives the result

hard to get into more detail in a discord message

its not really elementary anymore, just wanted to mention it

(fwiw its not trivial to even show that the sum of the reciprocals of all the primes diverges, that was shown by euler and dirichlets proof builds on those ideas)

[vernal dome]

In proving $\operatorname{card}(\mathcal P(\mathbb N))=\operatorname{card}(\mathbb R)$, one can construct a surjection from $\mathcal P(\mathbb Z)$ to $\mathbb R$ by $g\left(A\right)=\log \left(\sum _{n\in A}2^{-n}\right)$ if $A$ is bounded below and $g(A)=0$ otherwise. \

I have doubts about whether or not $A\mapsto \sum _{n\in A}2^{-n}$ is well-defined or not. Call this map $f$. I recognize $f$ as the binary expansion of a real number, but it was some time ago I looked at this stuff. Basically I want to verify that for the pairs $(A,r_1)\in f$ and $(A,r_2)\in f$, we get $r_1=r_2$. How can I do this?

[sterile pumice]

psie

[forest plank]

Because the sum is ≤ the infinite geometric sum of 2^(-n) which famously converges, so this converges too. Then, use the fact that if a series (sum) converges, its limit is unique.

[vernal dome]

yes, I'm ok with convergence, I'm just worried about stuff like 1.000... and 0.999.... If there was a set that mapped to both of these, we'd still say it mapped to a single number, right? That is, 1.

[torn escarp]

if something maps to two things and those two things are the same thing, then it just maps to a single thing

[vernal dome]

I see. Well, I still do not quite see how we can be sure about that something maps to two things that are the same, i.e. could there be a set that maps to two things that are not the same?

[feral olive]

Help me there is over 50 steps and i ignore wiche find is wrong!!! I am looking for a and b such as au+bv = gcd = 6

Edit even the gcd is wrong. It should be 43

🥲

[charred roost]

Why are you calculating the GCD of 11 digit numbers by hand?

[trim iron]

Skill

training

[forest plank]

If it's not just for fun and is actually an assignment, lol, then this is literally torture. 🫣

Up there with calculating the Jordan normal form of a 7x7 matrix

[feral olive]

exactly

[trim iron]

now do it mentally

🔥

[feral olive]

absolutely the worst suff are:
1- the book exercice show me very big number!
2- the book is recommended by ... me for self learning

[feral olive]

the fire = symbol of motivation or of burning in hell?

[trim iron]

whichever you prefer

[charred roost]

Are you trying to get better at arithmetic or at number theory?

[feral olive]

number theory I imagine

[trim iron]

the correct answer is arithmetic

[feral olive]

trough it is calculation

[charred roost]

if you want to get better at number theory, don't calculate the GCD of 11 digit numbers. That's arithmetic

[trim iron]

see

it's a trap

[forest plank]

A good exercise would be to write a program that calculates the gcd and coeffs for ax+by=1

[ivory cosmos]

use the digits 2,4,5 and 7 each once to create two prime numbers. What is the smallest possible product of two prime numbers created from these digits.

not possible right?

all the combinations are 3 mod 6 and thus can't be prime

am i misinterpreting?

[west glade]

what is meant by "create"

[ivory cosmos]

that's what the question states

idk either

i feel like you put the digits together

Lol

which can't work? Am i being dumb

[west glade]

well then you have to take either the 2 or 5 as a single number and then the other three with 7 at the end

and hope those three happen to form a prime

[ivory cosmos]

i'm confused, don't they say you have to use each digit once?

can i just take "2" as a single number

wait...

u mean 2 and a 3 digit prime number without 2, like that?

[west glade]

for example you could have the two numbers 2 and 547

i dont know if 547 is prime

[patent acorn]

it is

[ivory cosmos]

it is?

,w 547 is prime

[sterile pumice]

Results provided by WolframAlpha

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

Requested by mmmm70177

[ivory cosmos]

oh... wait aren't all primes +- mod 6?

oh 547 mod 6 is 1, whoops...

[west glade]

except the obvious exceptions, yes

[ivory cosmos]

so it's 2 and 457?

the smallest possible product?

4 and 257 for example could work but uhm that's bigger than the product of 2 and 457

[west glade]

and 4 isnt prime

[ivory cosmos]

oh yeah i'm dumb

but my answer is right, correct?

5 and 247 is bigger

[west glade]

if we are interpreting the question correctly, yes

[ivory cosmos]

was our style of solving the problem correct?

sorry not correct i mean efficient

did you have to know primes mod 6 = +- 1

[west glade]

no

[ivory cosmos]

otherwise it would be a tedious case to test all sqrt(number), no?

[west glade]

you have to know that those random three digit numbers are prime

prime => +-1 mod 6 but the other direction is false

so that doesnt help

[ivory cosmos]

yep makes sense but we don't need the other direction right?

since we have the three digits to test and we just mod 6

[west glade]

well it seems like you are trying to use it

[ivory cosmos]

oh i was just using it for all the three digit numbers we had

[west glade]

testing mod 6 is just testing mod 2 and mod 3

[ivory cosmos]

i mod 6 and expect +- 1

[ivory cosmos]

yep

[west glade]

well but that doesnt tell you whether the number is actually prime

it just eliminates the most obvious numbers, those divisible by 2 or 3

[ivory cosmos]

ohhh so i have to do a bunch of calculations too right?

[west glade]

yes

[ivory cosmos]

,calc sqrt(457)

[sterile pumice]

Result:

21.377558326432

[west glade]

tho tbf, the sqrt is like at most 25ish, so not too many primes to check

[ivory cosmos]

oh

[ivory cosmos]

okay so just 457/(primes < 21)

and so on right?

okay makes sense

[west glade]

yes

[ivory cosmos]

thanks

[obtuse quartz]

I'm looking for a "nice" prime modulus
Which can represented by
a * 2^b ± 1
Where b is relatively large and a is small.
As an example, 2^61 - 1 is a mersenne prime and a is small; 1.
And for 2^n ± 1 modulus, we can take modulo of a product quickly in programs too.
But here is the problem, I need -1 to be a quadratic residue under that modulus (let's call p), and to do that p needs to be congruent to 1 mod 4.
And if I want to find p in a form of 2^n + 1, only a few has been found. up to n = 16. Which might not be enough size (preferably n should be close to 1 or 2 computer words, from 64 to 128 on most machines.)

[torn escarp]

you can drop the ± and just put + since for b relatively large (larger than 1 lol) it will reduce to ±1 mod 4 and because -1 = 3 mod 4 is not what you want.

[forest plank]

For what purpose is this? 🤔

[errant otter]

Erm... anyone knows more about what this "famous result" is

[bold badge]

Shoenfield’s theorem I think

[errant otter]

Oh, interesting

[dry knot]

the standard peano arithmetic are defined from sets which dont require choice

we do need the axiom of infinity for the successor to be closed

the standard von nuemann ordinal or church ordinal are defined entirely from the empty set

uh not church, church is pure function i think

whatever theyre equivalent

[errant otter]

XD

[dry knot]

wait wait wait

yes pa, but does your class not do well-ordering?

well ordering is equivalent to choice

thats my only issue with this statement

i guess you dont need well ordering to prove important results in number theory, but idk why you would handicap yourself like that unless youre doing constructive mathematics

[errant otter]

yeah I'm quite sure that's like the only mention of choice in the course notes so it's just someone being pedantic or smth and not something we need to pay attention to

[dry knot]

i see

every heard that any subset of natural numbers has a least element?

this fact literally proves the axiom of choice

[errant otter]

yeah

[errant otter]

what in the logic

[dry knot]

https://en.wikipedia.org/wiki/Well-ordering_theorem

theres a proof here

[errant otter]

I see

[dry knot]

i mean almost everything in my number theory course could be proven directly or by induction anyways

even though we werent allowed to use induction, which was kinda silly

[patent acorn]

...no it doesn't, given that it's true in ZF as well

it proves that there's a choice function for N, but the universe has a lot more than just that in it

[dry knot]

it can be true without being provable from wop

i just mean wop <==> choice

[patent acorn]

what this is saying is that, even if you use the axiom of choice for big complicated infinite objects, to construct things like a non-measurable subset of [0,1] or a well-ordering of P(R), as long as the result is about natural numbers, the entire proof can be done with no AC at all

[patent acorn]

yes, the statement that every set has some well-ordering is equivalent to choice

this is very very different from the statement that the usual < relation on the natural numbers is well-ordered

[dry knot]

i see

[errant otter]

oh that's a neat to put it now the statement makes sense without me having to look at funny set theoretic logic stuff

[patent acorn]

the basic idea of how you prove this is that you interpret the proof as being inside L, the "constructible universe"

so when the proof asks for a choice function on "the real numbers", all that you actually need to provide is a choice function for the real numbers that are in L, and it turns out you can explicitly write down a choice function on L

then at the end you observe that the natural numbers in L are just the natural numbers

the technical details of exactly how you construct L are, uh, complicated, but you can just treat this as a black box of "when dealing with natural numbers you don't need to worry about AC"

[dry knot]

LOL i was confused here, wo of < on N is equivalent to induction, caused my mix up

[hollow dock]

Well-ordering theorem

Oh wait

Dead discussion, sorry

[meager reef]

Does there exist any integer n > 1 such that

[sterile pumice]

Riku

[meager reef]

I tried to find a closed form of this sum and it doesn't seem like there is one

I also thought about showing the gcd of numerator and denominator of the sum to be 1 but I am unable to follow through the induction hypothesis

[feral olive]

what does the exercice means with the part 3 of 12.A) please? It is just a question about english. not math.

[meager reef]

It basically is telling you to divide the number g by y

How you implement that depends on your programming language, in some the operations are already there

[feral olive]

euclidean division or floating number division please?

[feral olive]

python but it is not an issue lol!

b = 444


def prog:
    u = 1
    g = a
    y = b
    if y == 0:
        v = (g - a*u) / v
        return (g,u,v)

    #g / y ?```

[meager reef]

The following phrase in that line you asked about clearly states it's Euclidean division.

g = qy + t

[meager reef]

If it's python then

// operator returns quotient

% operator returns remainder. Store these in variables and repeat it through recursion. Should be faster

[meager reef]

If anyone sees this, thank you. Any help is welcome

[feral olive]

@meager reef in this case, what is the v ariable name for quotien and for remainder that are stated in the sentence?

[sterile pumice]

Riku

[meager reef]

Here we are dividing x by y

q is the quotient

r is the remainder

Remainder is always strictly less than y

The integers q and r here are unique for a pair (x,y).

[meager reef]

So for your case, quotient is q and remainder is t, which you can see by directly compairing the sentence with the definition.

[feral olive]

great! the the code should be:

a = 123
b = 444


def prog:
    u = 1
    g = a
    y = b
    if y == 0:
        v = (g - a*u) / v
        return (g,u,v)

    r = g % y
    t = g // y

?

[forest plank]

Let $s$ be this sum $1 + 1/3 + ... + 1/(2n-1)$.

Let $l$ be the highest power of 3 among the denominators in this sum. It's easy to see that there is only one fraction that has this highest power of 3 in the denom.

If we multiply the sum by $3^l$, it will become 1 + sum of fractions, whose denominators are all not divisible by 3, and nominators are all divisible by 3.

So, when we bring all the fractions into the common denominator, the denominator will be not divisible by 3, and the nominator divisible by 3.

In other words, we'll have $3^l \cdot s = (3a)/b + 1$.

Rearrange a little bit

$(3^l \cdot s - 1)b = 3a$

Left side not divisible by 3, right side divisible by 3. Contradiction

[sterile pumice]

🤗🤗

[meager reef]

Ohhhh that's very clever

Thanks a lot

I didn't even think in this direction

[runic token]

if you've seen the (similar) proof that $\sum_{k=1}^n \frac{1}{k}$ isn't an integer for $n>1$, this is basically derived from it

[sterile pumice]

valley

[feral olive]

Hello. Where is the soluce to this exercice from the book introduction to mathematical cryptography please?

[forest plank]

Well.. just remember what is the definition of x=y (mod m)

[charred roost]

don't post the same question in multiple channels

[feral olive]

sorry I will not do it anymore

[feral olive]

it is fir y divides m, there is a remainder x

then m = xy

no

[forest plank]

Does the book give any definition?

[feral olive]

probably I forgot to read a chapter can I tell you tomorrow please?

[forest plank]

Ok ☺️💫

[bold badge]

x≡y (mod m) means the remainder of x/m equals the remainder of y/m

[stiff rivet]

this definition can cause issues

its better to define it via m | (x-y)

[white lion]

why?

anyways it is still a useful heurisitc regardless

[stiff rivet]

it depends on the algorithm you use for performing division

the choice of remainder is not unique

e.g. you could choose remainders in {0, 1, ..., m-1} but also {-m/2, ..., 0, ..., m/2}

[west glade]

well either way you would choose the same one for both divisions

[white lion]

fair enough

[stiff rivet]

eh, there are implementations where you get wrong results

-1 not being equivalent to m-1

its a bit weird to say -1 divided by m is -1 with remainder m-1

[west glade]

well just because we arent as intuitively used to dividing negative numbers with remainders

[forest plank]

In what "implementation" do you get a wrong result 🧐

[stiff rivet]

some programming languages produce negative remainders on negative inputs and positive remainders on positive input

in general there is no correct choice when you pick a residue, so its better to "make all choices at once" and use the correct definition

[meager reef]

I came across the question after the previous one, and I used a similar idea to solve it

[severe ermine]

How should I go about this problem? To give you some context the chapter is about Binomial Theorem when the previous one was about Induction. Do I need to expand the left side and then do some algebra to get the right one or what?

[forest plank]

Well yes

[crystal agate]

try a combinatorial argument