elementary-number-theory

[manic mortar]

Hansel and Greta lemma

[charred jasper]

If you have f(x)=0modp^n you can find y st f(y)=0modp^n+1

here it's much less useful cause ofc 216=2^3*3^3 isnt prime

I got that x=4mod6 but like

That fucking sucks

[manic mortar]

i dont know this stuff

[charred jasper]

yeha i didn't expect you to, mostly i was hoping you would point out something obvious i missed like the symmetry

Anything obvious for the last one?

[manic mortar]

uhh no except maybe writing it like x(x²-2)+7 might help, idk tho

[leaden swan]

Can't you just like solve for mod 6, then generalize to mod 36, then to mod 216?

[charred jasper]

Yes

But this is something I should theoretically be able to do by hand, and I don't particularly want to find 197^2 or whatever

[leaden swan]

Have you tried using the fact that if {r_i} are all the solutions of f(x)=0 mod (a^k) then all the solutions of f(x)= 0 mod (a^{k+1}) will be of the form c a^k + r_i for some r_i and that you can deduce c by substituting and solving a linear congruence?

[charred jasper]

yes

my central problem here is thst i just refuse to use a calculator or something, so im just going to do that

[leaden swan]

Well I don't think there is an easier way than that

Well in particular,I mean this

Like you can enumerate all the solutions(what values of c gets you a solution, basically) generated for each r_j

And do this recursively

Ok this can be written as
$\frac{f(r)}{n^k} + c f'(r) = 0 \mod n$

[sterile pumice]

DraK

[leaden swan]

So for your first question
x=1,2 are solutions in mod 3

For mod 9,
If we consider r=1, -2+(2) c = 0 mod 3, so x=4 mod 9 is a solution

If we consider r=2, -1+ 4c = 0 mod 3, so c= 1 and x=5 mod 9 is a solution

Then consider for mod 27,
If r=4 mod 9, then 1+8c=0 mod 3, implies c=1 gives you the solution , that is c=13

If r=5 mod 9, then 2+10 c = 0 mod 3, c=14 is a solution

Second is more annoying because n=6 but same process should apply

@charred jasper So does this seem useful? Or is this what you were doing before?

[charred jasper]

Ok this is definitely cleaner than my previous process

Tys

[leaden swan]

Also being able to reduce to this doesn't depend on n being prime

It's just substitution and binomial

[verbal cedar]

if $q$ is a prime, how can i prove that

$qm\equiv 1\bmod{qk}$

has no solutions for $m$?

[sterile pumice]

nilpotent nix (nix)

[leaden swan]

A solution implies qk | qm-1

Which implies q | qm - 1 => q|1

[verbal cedar]

that makes sense, thank you

[daring ibex]

seems like the fact that q is a prime didnt matter at all

as long as q isnt 1 it holds true

[warm timber]

The last two digits of 9^1500 are "01." I proved it by observing 9^10 has "01" as its last two digits. Then used inducted to show 9^(10k) has last two digits 01 for all k. But I know there's a better way. Any suggestions?

[still flare]

You don't need induction to prove the last bit; it is obvious if you just work modulo 100.

I'm not sure which better way you're referring to. You could try and use Euler's theorem on the totient function, but it doesn't help more than just observing that 9^10 is 1 mod 100.

[wooden glen]

"Better" could mean a shortcut to 9^10 == 1 (mod 100), other than computing 9^10 = 3486784401 explicitly.

For example:

1. obviously 9^10 == 1 (mod 4).
2. we have 9^10 = 3^20 == 1 (mod 25) due to Euler's theorem.
3. thus by the Chinese residue theorem 9^10 == 1 (mod 4·25).

[loud moon]

I mean if you’re going to use Euler’s theorem you can just note carmichael(100) = 20 and go straight to step 2 and conclude

it does feel somewhat pointless to try and streamline this further

[wooden glen]

I didn't do that for the silly reason that the Carmichael-function version doesn't have a named theorem to refer to. 🙃

[warm timber]

10.) I proved that for all m>n^2 we have Euler phi(m) not equal phi(n) and 10.) would be a corollary of that. Here's my proof. Seem valid?

[primal escarp]

What is the contradiction?

[eternal sluice]

I love number theory

but I dont understand it\

[verbal axle]

Does this show that if $S \subset \mathbb{N}$ is an infinite subset then there is a finite subset $F \subset S$ such that $\gcd(S) = \gcd(F)$? If this doesn't work please just lemme know that it works, dont tell me why it doesn't work nor how to fix it

[sterile pumice]

ForJoke

[verbal axle]

<@&286206848099549185>

[sacred junco]

“Use the well ordering principle to prove that the gcd of a n integers is an integer linear combination of these integers”

I am having trouble figuring out what the set of counter examples should be for the well ordering proof.

[west glade]

why counterexamples

consider the set {linear combinations of these integers}

[sacred junco]

Thank you, I am new to proofs and the template I have been following for well ordering is to assume a non-empty set of elements for which what I am trying to prove is false, using well ordering to assume a least element then finding another element that is smaller than the least element which contradicts the assumptions and allows me to conclude no counter examples exist.

[verbal axle]

Is this true ?

[verbal axle]

<@&286206848099549185>

[still flare]

It does work.

[verbal axle]

thank you 🥰

[verbal cedar]

if $q$ is coprime to $n$ (not necessarily prime), then is $q^{\phi(n)-1}$ a general formula for $q\inv\bmod{n}$?

[sterile pumice]

nilpotent nix (nix)

[still flare]

Yes, the two will be equal modulo n

[verbal axle]

How was the conclusion that as n goes to infinity the gcd goes to gcd(S)?

Is it even valid to say “as we include all elements in S eventually”?

[primal pewter]

@verbal axle that reasoning sounds circular

and I don't buy that argument either

[verbal axle]

Which one?

[verbal axle]

This one?

[primal pewter]

the one with "as we include all the elements"

[verbal axle]

How so?

[primal pewter]

I mean, this is the argument that I don't buy

The circular one is the one regarding the convergence of the sequence.

[verbal axle]

I think the convergence can be shown by the fact that the set of all gcds is closed in R

Cuz it’s finite

[primal pewter]

it can be proved by Weierstrass (the sequence is non increasing and bounded)

[verbal axle]

That too

[primal pewter]

then, a convergent sequence with integers elements must be stationary

this can be proved just like they did

[verbal axle]

I’m confused as to how it converges to gcd(S)

I’m convinced that it converges

But how do we know it converges to gcd(S)

[primal pewter]

the key is that the sequence must be constant from some rank;
Let l be the limit (clearly an integer). Then there is N s.t. for all n>N we have |x_n - l|<1. This implies x_n = l for all n>N.

[verbal axle]

Ok

Now the only step left to understand is that l = gcd(S)

[primal pewter]

I think there is also a problem with this gcd(S). We can define the gcd of a finite number of integers. But for an infinite number of integers this sounds like a limit.

so maybe this is another circularity

I actually think that gcd(S) should actually be defined as that limit 🤔

[still flare]

No. In any nonempty, bounded set of positive numbers, there is a greatest element. Therefore the greatest common divisor of any (nonempty) collection of integers exists.

[verbal axle]

The issue is in this case S is infinite, but I guess it’s bounded below

[primal pewter]

Yeah, but I'm talking about the way it is defined. It should be a recursion.
Just like gcd(a,b,c) can be defined as gcd(a,gcd(b,c)), then gcd(a,b,c,d)=gcd(a,gcd(b,c,d))

[verbal axle]

Oh but the set of possible divisors is bounded above by the minimal of S

Honestly the way we did it is it’s the max of all {x such that x|s for every s in S}

[primal pewter]

so the classical definition of gcd

[verbal axle]

Yeah

[primal pewter]

it makes sense then

I think I've got it

so the sequence looks like this
x_1, x_2, ... , x_N, l, l, l, l, ...

and x_(i+1) always divides x_i

this is going to imply that l divides all the x_i

so we want to prove that l is maximal

if gcd(S)>l, then we have a contradiction, because gcd(S) divides every element of S, so in particular it divides

the gcds formed by s_1
s_1 and s_2
s_1 and s_2 and s_3

and so on

so it divides gcd(s_1,s_2,...,s_(N+1)), which is l

hence a contradiction

[verbal axle]

If l is smaller than the gcd I think we’re already done cuz it’s outside the set of these gcds

Also isn’t the sequence bounded below by gcd(S)?

[primal pewter]

it is

so parts of my solution are not necessary

[verbal axle]

ok so what I have so far is that the set G = {g | g is the gcd(A) where A is some subset of S}

G is bounded below by gcd(S)

So every sequence of members of G are bounded below by gcd(S)

Now how is l > gcd(S) impossible?

[primal pewter]

so l divides every s_i, but gcd(S) is by definition max{d : d divides all s_i}
this implies l<=gcd(S)

and we should combine this with gcd(S) | l to obtain gcd(S)=l

I think this is the solution

[verbal axle]

wouldn't this show that gcd(S) <= l

?

or am I tripping?

[primal pewter]

the first one implies l <= gcd(S) because S is the maximum over all those d; and l is one of those d's

[verbal axle]

OHHH

I see

so l < gcd(S) is impossible since G is bounded below

and since gcd(S) | l then gcd <= l

and we have that l <= gcd(S)

so gcd(S) = l

[verbal cedar]

anyone know of any uses of the jacobi symbol? i mean except maybe as an intermediate step of calculating a legendre symbol, or showing that a quadratic doesn't have any solutions mod n (not prime). but it just overall seems kinda useless

[dreamy steppe]

number theory question if anybody knows:
let's say we have an integer x
A = { all numbers less than or equal to sqrt(x) }
B = { all numbers greater than sqrt(x) }
is at least one integer in the set A going to be a factor of a number in the set B?
https://www.codewars.com/kata/5262119038c0985a5b00029f
(context of my question)

[still flare]

Yes.

Trivially in fact: 1 is always in A.

[sacred junco]

does anyone know how to approach this question? i get that the idea is that 150 divides any number which at the very least shares the same prime factorisation as it, but i’m not sure how to express this or to answer the question

[normal heart]

Consider 150=2*3*5^2

[dreamy steppe]

thanks

[dreamy steppe]

do you happen to know if there's a proof for this?

[still flare]

If x > 1, then sqrt(x) > 1. QED.

I assume you're implicitly having x>1, since otherwise the first set is empty.

[dreamy steppe]

sorry, i meant for my original question

[sacred junco]

then should i say that (with p standing for prime number):

k=2 x 3 x 5^2 x p1 x p2…

or should i go about it some other way?

[dusty dragon]

You only need to consider the powers of each of the primes that appear in the prime factorisation of 150

it might help to think about the prime factorisation of integers that are divisible by 150 (e.g. 150, 300, 450)

[sacred junco]

ok thx i’ll try and think of it in that way

[verbal cedar]

suppose $0<r<q-1$ and $q>2$ is prime. anyone have any clever ideas for ways to find integers $x,y$ such that $qy-rx=1$? Maybe using the $\phi$ function?

[sterile pumice]

nilpotent nix (nix)

[leaden swan]

Can't you just do extended Euclidean

[verbal cedar]

yeah ofc but i was wondering if there were any closed form solutions

for example, i know $y\equiv q^{\phi(r)-1}\bmod{r}$ and $x\equiv -r^{q-2}\bmod{q}$

[sterile pumice]

nilpotent nix (nix)

[sacred junco]

If x<y and x doesn't divide y then gcd(x,y)=1 right?

[leaden swan]

6 doesn't divide 9

gcd(6,9)=3

[sacred junco]

Ok thanks

[verbal cedar]

true if y is prime

[verbal axle]

Could I get a hint towards a more "elementary proof" of this?

[leaden swan]

@verbal axle

So you consider F = {a_1} ,where a_1 is smallest element in S. Now consider H={x | x \in S and gcd(F) doesn't divide x}. You can pick elements from H and put it in F until it works

[verbal axle]

How are we convinced that this process is finite?

What I was thinking is the following: Let G = {x | x = gcd(A) where A is a finite subset of S}

G is bounded below by gcd(S)

[leaden swan]

Well that is your task to figure out

Hint: this process terminates in atmost a_1 steps

[verbal axle]

What I mean here is that gcd(S) is a lower bound, and not the minimal element

[verbal axle]

I see, right cuz worst case scenario is that we are left with coprime sets

[leaden swan]

Wdym by coprime sets

gcd(F) will divide all elements in S, at the end of this algorithm

[verbal axle]

I don’t really know how to put words to what I have in mind

I’m sorry but I will come in around 15 mins, sorry once again

[leaden swan]

"pick an element in S. Form a set F. Try to find an element that is not divisible by gcd(F). If such an element exists, expand F to include that element"

If it doesn't exist, F is what we want

Repeat till we get our F

[verbal axle]

I was talking more about the termination process

[leaden swan]

Well so at each iteration gcd(F_new) is a factor of gcd(F_old)

[verbal axle]

Interesting approaches to the same problem all around

[verbal axle]

Thank you

[leaden swan]

So a_1 steps is like a very bad upper bound

[verbal axle]

I think sqrt(a_1) is better?

[leaden swan]

Well if a_1 is \prod p_i ^ k_i, I think it would be \sum k_i

Like at each step, you strip away exactly one prime factor

[lapis thistle]

I thought of an interesting integer sequence

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 23, 45, 67, 89, 102, 345, 678, 679, 801, 923, 945, 1023, 4567, 4568, 7012, 8039, 9123, 45678…

[verbal axle]

If I have an infinite subset S of N then I consider the set G = {g | g = gcd(A) where A is a finite subset of S}, G has a minimal element l = gcd(A). Now l is minimal iff l = gcd(A) = gcd(A U {x}) for any x in S\A, so does this mean that l must divide every x in S?

l = gcd(A) = gcd(A U {x}) for any x in S\A this parts comes from the fact that gcd(A) >= gcd(A U {a})

so if its the minimal it should remain the same

[open mist]

Yes it divides everything

[verbal axle]

so we can conclude that, l | gcd(S)

interesting

[elfin tusk]

NERDDDDDDDDDDDDDDDDSSSSSSSSSSSSSSSSSSSS

[verbal axle]

https://tenor.com/view/upset-sad-destroyed-i-give-up-gif-10215247

[patent acorn]

what were you expecting? this is literally a maths server

(oh they left)

[verbal axle]

how will I ever recover from such an accusation?

[unborn bough]

https://tenor.com/view/daeth-funi-periflight-dies-from-gif-22212023

[unkempt void]

Wait til you find out #advanced-number-theory

Oh

[upper venture]

is this system solvable?

[teal pelican]

first implies x is even and second implies odd

[upper venture]

yes

does the third one matters

[leaden swan]

Well no but that's because this has no solution

[upper venture]

even tho when there is 3

we check the g.c.d pairwise?

and if one pair have no solution then it not solvable?

[sharp kayak]

is that read “x is congruent to 10 mod 8” or is this something else

[upper venture]

8 mod 10

second one is 9 mod 12

[sharp kayak]

gotcha

[upper venture]

third is 5 mod 13

so we agree no solution for that right?

[patent acorn]

yep, no solution
x would have to be both even and odd which isn't possible

[analog onyx]

10 mod 8 makes no sense

[sharp kayak]

well, wouldn’t you just reduce it to 2 mod 8

remainder

[analog onyx]

i would yup

it’s easy enough that we don’t really ever write it that way

[sharp kayak]

right right

[analog onyx]

sometimes going into the negatives is helpful though

i used that for the little bit i’ve done on linear diophantine equations as well as polynomials reducibility

[upper venture]

talking about diophantine

lol

[analog onyx]

i worked in two variables so let me think

[upper venture]

im trying it as we speak

[analog onyx]

well you need the gcd(5,18) to divide 7

but 7 is prime so you’re good

apply page 6 and 7

[upper venture]

hmmm

i got x = 18k + 5 and y = -1-5k

sub x into second equation to solve for z

do i just leave that in fraction?

[analog onyx]

reducing the second equation mod 7 gives 5z = 5

back-substitution into that equation gives x=-1

[upper venture]

wut

how did u reduce it mod 7

[analog onyx]

7x is congruent to 0 mod 7

12z is congruent to 5z mod 7

and 5 is of course 5 mod z

[upper venture]

dont u only pick one?

[analog onyx]

pick one what?

[upper venture]

so this is what i got from first equation

dont i just need to sub x into the second eq to find general solution for z?

[analog onyx]

try it and see

[upper venture]

but i cannot reduce it

[analog onyx]

i’m not super confident in the way that you’re trying to do it, but the system doesn’t have a solution

[upper venture]

So how would u prove that it doesn't have a solution?

[patent acorn]

i'm fairly sure it does

x = 23, y = -6, z = -13 is one of them

[analog onyx]

z = 1 and x = -1, sub x = -1 into the first equation and get 18y = 12

[upper venture]

Oh bee, how did u work out z?

[analog onyx]

what’s wrong with the way i’m approaching it then? why does it fail

oh it’s finding the smallest solution not all of them. duh

[upper venture]

no im find the general solution of them all

what bee said is but one of the possible solution for x, y and z

[patent acorn]

i have no idea how either of you are approaching it, i kind of just invented a method from scratch and it worked somehow

[upper venture]

SMh

[analog onyx]

here wait i think i’ve got it let me get some paper

[upper venture]

plssss pick up from the last part of my z

we almost got this outttt

[upper venture]

pick up from my last lineee

[patent acorn]

alright well, 126k + 35 + 12z = 5

so 126k + 12z = -30

21k + 2z = -5

2z = -21k-5

[upper venture]

-15

[patent acorn]

?

[upper venture]

oh wait ur right

im wrong

LOL

[patent acorn]

...ah i see what's happened

if k is even, there is no value of z that makes the second equation work

so k has to be odd

which means you need to go back and change your x and y, replace k with 2k+1

then when you also do that here, you get 2z = -21(2k+1)-5 which will have a solution

[upper venture]

let wait and see what Jaxon got to say

[patent acorn]

(btw my general solution is x = 36k+17, y = -10k - 6, z = -21k - 13
i don't know how to check if that's all of them but i think it probably is, i've also checked that for -100 < k < 100 it does actually produce solutions by just writing code to check)

[upper venture]

HM thanks

[analog onyx]

that’s right yeah

[upper venture]

so u agree with replacing

2k+1

to produce those general solutions?

[analog onyx]

it’s gotta be odd

[upper venture]

kay thanks

[analog onyx]

what i was trying to do initially was get the smallest solution, not all of them

[upper venture]

this should prob go on the abstract algebra channel

[patent acorn]

yeah that's definitely abstract algebra

[cloud patrol]

Hi, what does this mean? Im trying to prepare for an exam ahead of time but I have no idea what this question is asking of me. I know how to find it for one number for some modulus but idk if its possible to find the order for 3 numbers?

The question (Translated to English):
Determine the order of elements 3, 5, 7 modulo 43.
Thanks 🙂

[west glade]

find the order for each element separately

[grim token]

can i prove that 8 | (m²-n²), m and n being odd integers and, i.e., (m²-n²) = 8q (q also an integer), showing that both 8q and (m²-n²) are even?

[wooden glen]

Showing they are both even is not enough to show that they are the same.

If you have the right concepts available, "work modulo 8" would give you a relatively slick proof.

Otherwise roll up your sleeves, write m=2k+1 and n=2j+1, plug that into m²-n² and start simplifying.

[grim token]

I did that, but what I got to prove was that (m²-n²) are even and that also 8q are even, I thought that knowing (m²-n²) equals 8q, it was sufficient to show that both are even

[wooden glen]

You should at least get slightly more than "even" when you simplify (2k+1)²-(2j+1)².

[grim token]

thank you, I guess that I reached the prove doing that. Is about finding "q" in terms of k and j and after that doing 8*q and showing that it's equals (m²-n²)?

[wooden glen]

I wouldn't worry about finding the q explicitly. It's a bit simpler (at least in my mind) to end the argument with "... and therefore it must be some multiple of 8" than to write down the quotient in a way that makes it obvious it's an integer.

[grim token]

Thank you very much

[thorn radish]

I cannot seem to find the idea for this Q

[dusty dragon]

Induction seems the most natural method

[thorn radish]

Even for the case n = 1

It is quite ugly

[primal escarp]

I think it will always be divisible by 47

[loud moon]

you can also get a hunch for 47 by looking for n such that phi(phi(n)) = 22, given the problem statement

[primal escarp]

Or by looking at n=0 ig

[loud moon]

lol that works too haha

[thorn radish]

I dont think this is true

32^23 mod 47 is congruent to 1 not 32

[primal escarp]

You first have to lift 5 to 22n+1

It is $2^{(5^{22n+1})}$

[sterile pumice]

Takumi

[thorn radish]

bruh

rip

💀

[thorn radish]

how do i calculate the congruence in this case?

[primal escarp]

You need to evaluate $5^{22n+1}$ mod 46$

[sterile pumice]

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

[primal escarp]

but this is easy since $\phi(46)=22$, so this is congruent to 5 mod 46

[sterile pumice]

Takumi

[primal escarp]

and then we just get $2^5+15=47\equiv 0 \pmod{47}$

[sterile pumice]

Takumi

[thorn radish]

hmmm

what congruence theorems are used here?

I have not taken any NT

I am just studying elliptic curves so I need to learn some congruence

[thorn radish]

why choose mod 46?

[primal escarp]

oh because of fermats little theorem $a^{46}\equiv 1 \pmod{47}$

[sterile pumice]

Takumi

[thorn radish]

ah okay

[primal escarp]

so it makes sense to reduce the exponent mod 46

[thorn radish]

this makes a lot of sense

[thorn radish]

and then you use Lagrange's theorem and euler totient function? to reduce it to 5?

[primal escarp]

yes, that is equivalent to euler's theorem

[thorn radish]

ah I have not seen euler theorem

maybe I just need to read

seems like knowledge diff

[primal escarp]

it's just a specific case of lagrange's

[thorn radish]

ah okay

yea

adds up

thanks!

is there a proof for this case without abstract algebra?

[analog onyx]

phi(n) is all natural numbers less than n and relatively prime to n ?

[thorn radish]

yes @analog onyx

[primal escarp]

yes, here is the one from wikipedia

[thorn radish]

oh nice

this is nice

took me only 2 reads to understand

and its an interesting result

[primal escarp]

yea it's pretty clean

[slow elbow]

Could anyone help me in how i would go about solving this?

I am familiar with the basics of the exponential cipher or RSA cipher but

am unsure of the method for this

[cloud patrol]

Hello, how would I go about solving this efficiently? State explicitly all the primitive roots of the number 43.
It seems absurd to try and check for all numbers between 1 and 42. Does anyone know a method that would be quicker?

[primal escarp]

There isn't really a better way than to do guess-and-check. Look here for example https://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number

[cloud patrol]

alright, thanks a lot

[cloud patrol]

How do you know this is right?

[still flare]

calculate phi(761)

[cloud patrol]

that would be 760

[still flare]

Right, my mistake, I assumed it would be simpler.

[cloud patrol]

no worries

[still flare]

There may be a nice method to show that via Carmichael numbers, but I don't know about them.

In practice you would just calculate 2^380 mod 761, which tbh is easier than it sounds

[cloud patrol]

that sounds quite impossible without a calculator, I gotta say

[still flare]

Not really

Here's a trick

[cloud patrol]

i cant find any resources online because my main language isnt english and idk how to translate from my language correctly as google translate isnt doing anything useful

[still flare]

calculate the base-2 representation of 380, then calculate 2^1, 2^2, 2^4, 2^8 etc mod 761. This isn't too hard as you're just squaring them.

Then you multiply these numbers together as dictated by the base-2 representation of 380

This simplifies the calculation immensely.

[cloud patrol]

youre right, thanks

[open mist]

Also 380 = 760/2 and 2^760 = 1
Hence 2^380 is a square root of 1, which is either 1 or -1 = 760
Then there's probably a trick to show it isn't -1
@still flare that's probably the intended method no ?

[still flare]

Maybe 🤷

[open mist]

380 is just too sus for it to be your method

[cloud patrol]

now i wonder what that trick is

this congruence stuff is so unintuitive to me idk why

[still flare]

I'm giving a general method, not an ad-hoc one :)

[cloud patrol]

it seems like you need to grab a pickaxe and just start whacking at the numbers until you get what you need lmao

[open mist]

a is a square in Fp iff a^(p-1 /2) = 1
Hence it suffices to show 2 is a square in F_761
Turns out it's the square of 73 (and 688)
Not exactly satisfying right now

[cloud patrol]

interesting approach

[open mist]

The last step bugs me

I want a clean solution, not one for which WA does the last step for me

[cloud patrol]

all my research has lead me to the conclusion that its all down to intuition and trial and error

[open mist]

Was this supposed to be done by hand ?

[cloud patrol]

done by hand? i suppose not, its an example i found online

i doubt anyone would give such an example on an exam

it just bugs me how the people using these examples to explain these concepts find these answers

and why the hell they use such examples lol

[open mist]

What was it for ?

[cloud patrol]

https://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number

im struggling to find an example for a smaller prime number like 43 or something

[still flare]

Try a way smaller prime, like 7

[open mist]

That guy certainly did it with a computer

[cloud patrol]

yeah just did, its pretty easy but we get examples such as 67 on our exams so Im trying to figure out how to do it efficiently

[cloud patrol]

yeah, seems impossible otherwise

[verbal cedar]

once you have one primitive root $g$ mod $m$, the other primitive roots are given by
$$\bdef{g^k:\gcd(k,\phi(m))=1}$$
so just get one, and then the others will be $g^k$ where $k$ is coprime to $\phi(43)=42$.

[sterile pumice]

nilpotent nix (nix)

[verbal cedar]

the best place to start is like 2,3,etc. in this case 3 is one.
you can use the legendre symbol to know if you shouldn't bother checking one (that is, don't check quadratic residues).

one trick you can use is if you find an element r of order (p-1)/2, and (p-1)/2 is odd, then -r will be a PR. since ord(-r)=ord(-1)ord(r)=2(p-1)/2=p-1

[slow elbow]

what does the phi notation mean?

[loud maple]

ϕ is the Euler totient function. ϕ(n) is the number of positive integers x less than or equal to n such that gcd(x,n)=1.

[cloud patrol]

Thanks so much

[slow elbow]

@kniwatch ah ok thank you

@loud maple so im guessing i would hgave to use the phi function (p-1)(q-1) in this case to find the awnser?

[leaden swan]

Well yes , there are phi(8023) possibilities

[slow elbow]

thank you!

[flat wind]

Would lemma 5.2.2 not also hold whenever $|f(n)| \leq k n^c$ for any $k \in \mathbb{C}$?

[sterile pumice]

CoffeeMan

[leaden swan]

Well <= doesn't make sense in \bC

[flat wind]

Ah, sorry, in R, I mean

[leaden swan]

Isn't C a real constant in the definition itself?

[flat wind]

Yes

[leaden swan]

mb

[flat wind]

But I don't see why the C has to be the same as the exponent

[leaden swan]

Oh it doesn't need to

[flat wind]

Seems to restrict it unnecessarily

[leaden swan]

I think they just used c and C for no reason

[flat wind]

Ohhh

Ahh, ofc

My eyes lol

Thx

[verbal axle]

what does it mean for a quadratic form Q to represent a number p?

Is it that there exists numbers s,t such that Q(s, t) = p?

[stiff rivet]

yeah

[prime gust]

I need to show that the Diophantine equation x^4-4y^4=z^2 has no solutions and if I can prove that the gcd(x^2,2y^2,z)=1 then I am done. but I don't manage to find a way to prove this

[verbal axle]

Thank you

[grim token]

Any tips in proving by induction that 1³+2³+...+n³ = (1+2+...+n)², for n >= 1 ?

[verbal cedar]

use the fact that $1+2+\ldots+n=\frac{n(n+1)}{2}$

[sterile pumice]

nilpotent nix (nix)

[grim token]

Thanks

[grim token]

I got it using this, thank you

[analog onyx]

make sure you prove the relation that you used by induction as well!

[dusty hound]

Been struggling on inequalities throughout my reading on "Elementary Number Theory 2nd ed by Dudley" but what are some good resources to grasp a good understanding of inequalities? It's one of the biggest barriers for me since I was always super terrible at inequalities.

I was having a difficult time understanding the last part of the division algorithm proof where -b < r-r1 < b and a few parts scattered throughout some of the proofs in the book

I'm at the point where I'm thinking about putting a hold on ENT and learning basic proofs and calculus first. I'm taking calc 1 over the summer and I have a copy of Stewart's 5e.

What are some struggles some of you all had in ENT?

[umbral tinsel]

Hello, i have a question. i wish to get help.

$\frac{x+a}{b} + \frac{x+c}{d} = e$

[sterile pumice]

kalite

[umbral tinsel]

rules: a, b, c, d, e, x are integer.
what is not okay:
a = b (equal to other variables)
a = -b
a = 3 ( a static number)
a = x (equal to x)
a = x + 1 ( linked to x)
a = 2x
a = x + b
what is okay even thought making them a lot is not good:
a = 2b
a = b + 1
a = b + c
a = b + k and c = k + 1
linking more than half of variables whic is 6/2=3 is not okay.
like a = b + 1 and c = d +e is good
like a = b + 1 and c = d +e and d = 2b is not good but okay
like a = b + 1 and c = d +e and d = 2b and c = 2a is not okay

i seek some constraints between a, b, c, d, e, for example a = b + 1, c = d + e

thanks for reading.

[umbral tinsel]

<@&286206848099549185>

it is like calling police 😄

[umbral tinsel]

anyone here ?

[verbal axle]

Wish I could help

but I dont seem to understand the question

[still flare]

I second that

[crude thicket]

OK I have those 2 inequalities:
({2^3 < 10 = 10^1})
({2^{10} > 1024 = 10^3})

[sterile pumice]

Benschko

[crude thicket]

and with them I have to determine the digits of the largest prime that has even been found:
2^{82,589,933} - 1

estimate sry. not determine

[still flare]

Your second inequality is wrong

[still flare]

It's still wrong

2^10 = 1024 > 1000 = 10^3

Anyway

[crude thicket]

so my prof fucked up?

[still flare]

If you would like a hint: to determine the number of digits of an integer, we want to find the highest power of ten which is a summand. What commonly-used function allows you to find the power of 10 within a number?

[still flare]

Your prof made a typo, yes

[crude thicket]

logarithm?

can i just plug that into the logarithm and get the result? so the log_10 is 2,5 x 10 ^7

so i have roughly 8 digits?

[verbal axle]

Could someone verify this proof?

here pi(n) is the number of primes less than n

nvm doesn't work

replacing 10 with e tho, that seems to work

[verbal axle]

<@&286206848099549185>

I want to find a bound of the form Cln(ln(x)) for pi(x)

[ancient crow]

how did you get the inequality on the right

the alpha /leq ...

[verbal axle]

Cuz there are at least alpha primes before the product of the first alpha primes

[gaunt sedge]

apart from testing all the numbers, how do i deduce that x^2 = 5 mod 25 has no solutions?

[void anchor]

you could reduce mod 5

[gaunt sedge]

i guess i could write an equation, rearrange to get x^2 = 5(1+5k)

[gaunt sedge]

doesnt that give me x^2 = 0 mod 5?

[void anchor]

This then gives you x = 0 mod 5

Then what is x^2 mod 25?

[gaunt sedge]

im confused, why only x?

[loud maple]

p|x² => p|x, for any prime p and any positive integer x (try proving this)

[gaunt sedge]

ah thank you

[gaunt sedge]

x = 0 mod 5 implies x^2 = 0 mod 25 ???

[loud maple]

Yes

[gaunt sedge]

so we have just done x^2 = 5 mod 25 => x = 0 mod 5 => x^2=0 mod 25 ?

[loud maple]

Yeah

[gaunt sedge]

isnt that breaking maths

[loud maple]

Have you not heard of proof by contradiction?

[gaunt sedge]

oh

suppose x^2=5 mod 25 .... then x^2=0 mod 25, contradiction, so has no solns

[loud maple]

Yes, exactly.

[gaunt sedge]

ok, thank you :3

[cloud patrol]

Hi, could anyone explain why for example phi(29) = 28 and phi(58) = 28 as well? (This works for every prime number I have tried so far)

[dusty dragon]

If p is prime, then every integer smaller than p is coprime to p. This tells you that phi(p) = p - 1

For 58, you can express this as 2 * 29. The phi function is multiplicative, so phi(ab) = phi(a) * phi(b) when (a, b) = 1. But since 2 and 29 are both prime, we have that phi(2) = 1 and phi(29) = 29 - 1 = 28 so phi(58) = 1 * phi(29) = phi(29) = 28

[cloud patrol]

makes perfect sense, thanks

[verbal cedar]

you can also think of it more straightforwardly. all the numbers 1-28 are coprime to 29. for 58, to be coprime, you have to be coprime to 29 and odd. so that means counting all odd numbers from 1-57 (and not including 29). so 1,3,5,...,25,27,31,33,...,55,57, and you can see there are 28 of them as well.

this principle applies to all odd numbers, though. if m is odd, then phi(2m)=phi(m) for the same reason.

[verbal cedar]

which can be proved more easily with this

[cloud patrol]

makes sense, appreciate the explanation.

[cloud patrol]

Hi, how do I prove that phi(n) = 10 only when n = 11 and n = 22?

[cloud patrol]

Could I use this somehow?

I need a sound proof

[wooden glen]

The totient is multiplicative, so if you have phi(n)=10, n must be a product of different prime powers whose totients multiply to 10.
So except for the obvious phi(11)=10, and factors with phi(n)=1 (which happens for n=2 only), you're looking for numbers with phi(p^k)=2 and phi(p^k)=5. In particular, one fairly easily sees that phi(p^k)=5 never happens: If k=1, then p would be 6 (which is not prime, a contradiction) but if k>1 then p | phi(p^k), but the only p with p | 5 is 5 (which is not its own totient, another contradiction).

[cloud patrol]

I see, I see. Thanks.

[white lion]

what does 58^23 (mod 9) even mean

I know what a is congruent to b in mod n mean but not this

[normal heart]

It's finding (a small enough) b, where you are given a=58^23 and n=9

[fallen leaf]

idk if this is the right area to ask this, but I'm stuck trying to prove the following:
let a & b be integers, then ab = 1 implies a = b = ±1. Trying to prove this WITHOUT ideals/abstract algebra...
I've tried a few different methods with induction but I feel like I'm overlooking a simple direct proof?

[verbal cedar]

i guess you could do by contradiction. suppose that |a|>1 (WLOG a>1). show that b is not an integer.
i guess it sort of boils down to proving 1/n is an integer iff n=+-1

[grim grotto]

Guys can anyone explain quadratic residue

[verbal cedar]

how can we determine if something can be written as a square mod n (i.e. is a=x^2 mod n for some x?)? how can we know if a quadratic polynomial has any solutions in a modular ring? those are questions we want to be able to answer. there you go, that's pretty much the idea.

look into the legendre symbol, eulers criterion, law of quadratic reciprocity, etc. if you want to learn how to answer those questions

[undone sundial]

I’ve been told to ask here. Anyone have any tricks to determining if a number is a factorial? I’m looking at huge numbers here. I’ve already been told large factorials have a bunch of 0s at the end. Any more advice?

[silver oak]

why would you need that 🤔

[undone sundial]

Curiosity

[leaden swan]

How big is the number in question

You can bound it above by a factorial, I think

[west glade]

you could just start dividing them by numbers that are getting bigger and bigger

[leaden swan]

And then just brute force

[west glade]

or from the number of zeros figure out after which multiple of 5 you are and then start dividing by the primes less than that

is that just the end or is that the whole number

[undone sundial]

How do you figure out which multiple of 5 it is?

[leaden swan]

That could be like 50! I suppose?

Count the number of digits in this and that

[undone sundial]

Whole #

[west glade]

that looks like way too many zeros for a factorial

compared to the whole number

[undone sundial]

?

[west glade]

https://i.imgur.com/5qn7Y85.png

just as a comparison for the number of zeros/other digits for 500!

you get a zero for each factor of 2 and 5

factors of 2 are easy

so you only need to count the factors of 5

you get one from 5, 10, 15, 20, 25, 30, ...

you get an additional one from 25, 50, 75, ...

and an additional one from 125, 250, ...

etc

[undone sundial]

Oof so pretty tricky to figure out the multiple of 5

[west glade]

ehh

I mean you dont wanna do this by hand

or do you?

[undone sundial]

Not at all

[west glade]

otherwise just run through a for loop and start dividing by 2,3,4,5,6,...

[leaden swan]

Actually you can do one thing

[west glade]

either you end with 1 or you dont

[leaden swan]

Check what v_5(n) should be

[west glade]

with python that would run within a second

[leaden swan]

That will give you 5 possibilities for what your n can be

[undone sundial]

You say this like it means something to me

[west glade]

(definitely not what I am talking about)

[leaden swan]

v_5(n) is greatest power of 5 dividing n

You can use that to figure out the greatest multiple of 5 <= n

[west glade]

aka the number of zeros in n!. which is what I am talking about

you could just do that with any number btw. the 5 is just nice because you could count the zeros

well nicer if you were to do it by hand

[leaden swan]

Yeah

[west glade]

for the pc you would wanna use bits and stuff

[leaden swan]

Well not really

[undone sundial]

Sorry you’ll have to dumb it down even more

[west glade]

lets do it the other way around for a sec

lets try to find the number of zeros of 31!

like mentioned earlier, we need to count the number of times 5 appears as a factor

if we write out 31! = 1*2*3*4*5*6*...*10*...*15*...*20*...*25*...*30*31 we can count the number of factors of 5

[undone sundial]

30, 25, 20,15,10,5?

[west glade]

there is one from the 5 in the beginning, then one from the 10, 15, 20, two from the 25 and then one again from the 30

so 1+1+1+1+2+1=7

https://i.imgur.com/crVPFVP.png

and if we calculate 31! we see that it has indeed 7 zeros

[undone sundial]

So 31! Has 7 0s at the end?

Ok

[west glade]

so and in theory we could reverse this whole process

[undone sundial]

So it would help to have a map premade like the one here going up to a crazy high number

[cloud patrol]

you dont need to do it manually tho

[undone sundial]

Then maybe like itertools.accumulate until you don’t go over the number of 0s

[cloud patrol]

you can automatically rule out any number where more than half of the digits are zeros

but still, just checking the number of zeros isnt enough to prove a number is a factorial of a number, or im wrong

[undone sundial]

The suggestion was to find the number of zeros, figure out which multiple of 5 it is, then divide by primes below that number… I think

[west glade]

one of the suggestions, yes

the other more stupid but way faster to code suggestion is to just start dividing by 2,3,4,5 until you end up with 1 or not

[undone sundial]

Yeah brute force.

That’s what I have now but it breaks before 33000!

As in, reversing the large number that should result in 33000!

[west glade]

wdym

[cloud patrol]

weird that it breaks if youre using the bruteforce method

is it a memory problem?

[undone sundial]

Maybe

[west glade]

python has no problem calculating 33000! so it shouldnt have a problem with this either

[undone sundial]

Checking if it’s 1000! Then 1001! Then 1002! Etc

Maybe I’m thinking about this wrong

Instead of calculating large factorials 33000 times and comparing them against my number, I should just divide the number starting from 2 and going up to 33000, right?

[west glade]

yes

wait did you start new again over and over?

[undone sundial]

😅

[cloud patrol]

no wonder it broke

[undone sundial]

It’s no secret I’m not very smart 😝

[cloud patrol]

hahha you got this

[undone sundial]

It makes sense when it’s said to you 😝

[cloud patrol]

some things that people find basic need to be explained a million times for me to understand so dont worry

[white lion]

how can they say x = 5+7(4) when k is congruent 4 mod 5 not equal to 4? meaning k-4 is a multiple by 5.

[cloud patrol]

i dont quite understand your question, but i guess the answer would be because the first number that comes to mind for k is 4, so 4 congruent 4 mod 5 is true, meaning that taking the value k = 4 and returning it to the substitute yields that answer.

[verbal cedar]

they're just giving you one value of k because that's all we need

x=5+7(5k+4)=33 mod 35 for all k

[grim token]

tips in how to find r?

[verbal cedar]

use fermats theorem. you're essentially trying to find

$(5^{198}-3)\bmod{7}$

[sterile pumice]

nilpotent nix (nix)

[grim token]

thank you!

[versed olive]

Does anyone have some resources on getting some more intuition about the möbius function and its applications? (sorry if this is the wrong channel to ask about it)

[swift hinge]

you can try "the theory of numbers by ivan niven" it contains a small section about mobius function and inversion and some decent problems related to it. This book is on elementary level so i think its worth mentionting it here.

[versed olive]

oh thank you!

[swift hinge]

[sacred junco]

I've been using that book in my number theory class and it's been alright, but I'm very sure there's better material out there concerning arithmetic functions

My course only had a single lecture on arithmetic functions and the book was more than enough for that but from what I can tell the book doesn't dwell on them for long either

[verbal axle]

how would we solve something like x^2 + x - 6 = 0 mod 77?

we can factor x^2 + x - 6 = (x-2)(x+3)

[still flare]

We solve it mod 11 and mod 7, then use CRT

[verbal axle]

so (x-2)(x+3) = 0 mod 7 and (x-2)(x+3) = 0 mod 11

?

and then take linear combinations?

[still flare]

I don't quite know what you mean by linear combinations here, but the point is that you could have a solution which is 2 mod 7 and -3 mod 11

this lifts uniquely to some value mod 77

[verbal axle]

i see

also since 7 and 11 are prime at least one of the factors of x^2 + x - 6 = 0 mod (7 or 11)

right?

[still flare]

Yeah that's right

Ofc we cannot conclude the same modulo 77

[verbal axle]

so we solve (x-2 = 0 mod 7 and x-2 = 0 mod 11) and (x+3 = 0 mod 7 and x+3 = 0 mod 11)

[still flare]

No, you also need to consider x-2 = 0 mod 7 and x + 3 mod 11, for example

that will still produce a solution

[verbal axle]

wdym x+3 mod 11?

[still flare]

x+3 = 0 mod 11

If you like, if x-2 is a multiple of 7 and x + 3 is a multiple of 11, then (x-2)(x+3) = 0 mod 77, so we need to consider these 'mixed' solutions.

[verbal axle]

oh so we actually have 4 equations?

[still flare]

We do.

[verbal axle]

sounds painful

is there a way to find all the solutions without having to solve so many equations?

[still flare]

Not that I know of

And it's not painful, just use the CRT

[verbal axle]

ok thank you

[still flare]

No worries

[verbal axle]

what if we have x(x-1) = 0 mod 105

105 = 3(5)(7)

[verbal cedar]

youd probably have to CRT into 3,5,7

8 solutions total so have fun lol

8=2^3. because you have 2 choices for what x is congruent to mod 3,5and7. 0 or 1

[verbal axle]

so we would have
(x = 0 mod 3, x = 0 mod 5, x = 0 mod 7)
(x = 0 mod 3, x = 0 mod 5 and x-1 = 0 mod 7)
(x = 0 mod 3, x-1 = 0 mod 5 and x= 0 mod 7)
(x = 0 mod 3, x-1 = 0 mod 5 and x-1 = 0 mod 7)
(x-1 = 0 mod 3, x = 0 mod 5 and x = 0 mod 7)
(x-1 = 0 mod 3, x = 0 mod 5 and x-1 = 0 mod 7)
(x-1 = 0 mod 3, x-1 = 0 mod 5 and x = 0 mod 7)
(x-1 = 0 mod 3, x-1 = 0 mod 5 and x-1 = 0 mod 7)

?

[verbal cedar]

yeah

[verbal axle]

ok

thank you

[verbal cedar]

once you do CRT once (finding the inverses and stuff) then it's just plugging stuff in

[verbal axle]

i see

[harsh loom]

How do I learn this?

Is there a book I need?

[leaden swan]

You want to learn CRT?

For general NT, Burton is considered to be a good book

[harsh loom]

Thanks

[leaden swan]

#book-recommendations message

[toxic island]

how do you work these out?

[stiff rivet]

"chinese remainder theorem"

[dense mason]

hey guys is there a particular algorithm i can use to prove a big number is prime? (aside from having no other prime factors)

there is this particular one where you compare the root of the number in question with the closest superior root that gives you an integer (like V169 or V289)

then you check if it has any prime factors inferior to the root

is that valid for any prime number?

[stiff rivet]

uhh

do you mean checking divsibility of all numbers up to sqrt(n)?

that works always, yes

but its far from the best way

[loud maple]

There exist deterministic polynomial time primality tests.

[verbal axle]

Ok I was tweaking

It’s not as bad as I first thought

[still flare]

I told you as well!!!

[verbal axle]

Oh yeah true 😊

It was just plug and chug

[cloud patrol]

Is there any proof regarding this in quadratic reciprocity?

Transforming this:

To this:

[stiff rivet]

you multiply each side by (q/p)

[cloud patrol]

how do the (q/p)*(q/p) on the left side cancel out after that?

[stiff rivet]

(q/p) is either 1 or -1

[cloud patrol]

in this case its always 1 then?

[stiff rivet]

?

1^2 = (-1)^2 = 1

[cloud patrol]

oh nvm im dumb, thanks

[tall shore]

I was thinking about the odds a number being prime and came up with the following intuition:

Every factor of a number can be found from 2 to sqrt(n). The odds that a number has a factor from 2 to sqrt(n) can be modeled by the following:

probability that n is divisible by some i is 1/i (there are i possibilities for n mod i and there is one possibility in which n is composite (n mod i = 0)). Thus the probability that a number is composite is 1/srt(n) * 1/(sqrt(n) - 1) *.....1/(2). This is equivalent to (sqrt(n)!)^-1. Thus the probability that a number is prime is 1-(sqrt(n)!)^-1.

However, as n increases, the probability n is prime increases as well, which can't be right. What's wrong with this logic? I've seen a couple number theory proofs but I didn't really understant them.

[west glade]

it doesnt need to be divisible by all numbers from 2 to sqrt(n)

just by one of them

[tall shore]

ohhh yea

rip that was stupid

thnx

[west glade]

happens ¯_(ツ)_/¯

[open mist]

The probability of a large number being prime may be approximated by using the pi function.
After all k is prime iff pi(k) - pi(k-1) = 1.
There's a theorem stating that pi(n) ~ n / ln n.
pi(n) - pi(n-1) is approximately the derivative of pi. This can be approximated intuitively by differentiating the equivalent, yielding (ln(n) -1)/(ln(n)^2).

i.e. the probability of n being prime is approximately 1 / ln n

And it adds up numerically of course

Between 1 and 1.01 million, there's 753 and the approximation gives 723
Between 1 billion and 1.001 billion there's 48 155 primes and the approximation of 1M / ln(10^9) gives 48 254

So it's pretty damn legit

[tall shore]

this has been the best explanation I've seen so far

thnx so much

[surreal crescent]

Call a positive six-digit integer tall if, upon removing any number of digits (not necessarily consecutive) from the number, the number, when read left-to-right, is always composite. How many such six-digit tall integers are there?
This problem might just seem like just finding the number of ways to arrange 4, 6, 8, and 9 in six places, but prime numbers can be created from these. For example, 499 and 449 are prime. I'm not sure how to deal with this overcounting issue, or how to track these primes.

[west glade]

problems that have weird rules like this rarely have nice solutions. I would throw a computer at it

[cloud patrol]

https://tenor.com/view/it-crowd-moss-computer-throw-gif-5404468

[surreal crescent]

lmao

[surreal crescent]

are there any interesting approaches that don't need coding that i should try?

[sterile pumice]

Capt_krunchy

[sacred folio]

Hola Math-a-mateers, I have a simple question for you and I was wondering if you point me to the mathematical principles underpinning this and how this could be generalized to other primes:

Mainly just think of this as a number guesser for numbers X and Y which are rejected using the criterion described, what is this number sieve using, how can it be expanded, etc. All help appreciated.

[loud moon]

do you have the full pdf? it's missing a lot of context

intuitively though a process that only ever divides by 3, 5 or 7 is not going to produce particularly interesting results

[sacred folio]

https://arxiv.org/abs/2210.14519

[sacred folio]

Yeah, so basically the idea is that you have a stochastic boltzmann machine providing trial solutions to factorise a semiprime.

The Boltzmann networks activation at some time step t is a candidate solution and then we run this mini-sieve to discard any immediately obvious nonsense and zero into a correct factorization more quickly.

So, the immediate question is, if you're going to scale this, you can use larger primes, but then the field of exploration from the provided candidate gets larger. So I was wondering if there was a number-theoretic way to confirm exactly how far from a candidate the machine would have to drift before you are wasting your time.

[loud moon]

I guess I just don't see why the divisibility information of these "candidates" by 3, 5 or 7 should help you "zero in" on the factorization more easily - unless the factors are 3, 5 or 7, the divisibility information seems to tell you nothing

[sacred folio]

Well, there's some clever probability theory that is letting the network tend to a solution and the sieve just accelerates that natural process.

[sacred folio]

And semiprime means product of two primes, so anything divisible by 3,5,7 probably isn't going to be it for most semi-primes.

[loud moon]

that's kind of my point, I'm not really seeing any justification in the paper qualifying the effect of that extra step and reasoning for why it should speed up the process, and how far exactly it can be pushed. the paper kind of reads like "we tried this and it seemed to help, here's some graphs". without further analysis my guess is that the previous method was just exceptionally slow and this new method fixed that issue and is now about as effective as picking a random number between 1 and N and hoping it's a factor, i.e. no worse than trial or error should be but no better either. at least that's how I interpret Figure 3, the method they are comparing against has a "number of samples to 50% accuracy" that is literally larger than the input number to factor 😦

[sacred folio]

Number of sample ops =/= time steps. Anywho, I don't want to get into the weeds over the computer engineering here.

Going back to the sieve, can you suggest how this might be expanded/theoretical limits of this?

[loud moon]

nope, but I'd be interested to know as well if someone else can

[sacred folio]

Couldn't add an extra prime-factor and then test a range as seen in the original excerpt?

[sacred folio]

To condense the question: Consider a number X, we intend to find a number X+a such that X+a is not divisible by the first n primes. What is the absolute upper bound on a such that there exists an X+a that is not divisible by the first n primes.

[sacred folio]

Tbqh, it's probably better to just answer this question probabilistically. The chance any given random number has a factor n is 1/n, then the chance that any given number doesn't have the first n-primes is:

,$ \prod_{i=1}^n \left(1-\dfrac{1}{p_n}\right)

[sterile pumice]

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

[sacred folio]

So, you can just set your bound to be:

,tex \text{argmin}a \left{2a\prod{i=1}^n \left(1-\dfrac{1}{p_n}\right) \geq q\right}

Where q is some confidence level

Lousy heuristic, but hey, it works for small enough n and large enough X.

[sterile pumice]

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

[sacred folio]

This is working under the assumption that I'll only ever find one candidate in [X-a,X+a] - so ymmv

[vast cliff]

What is the difference between the series sum sign and this pie?

[verbal axle]

sigma is addition

pi is multiplication

[fervent tangle]

if im asked to prove this in exam would it be safe to omit the examples (m!+2,m!+3) or would i need them

this is how the proof is given in my lecture notes

[verbal axle]

its a proof by induction, so you're good

[fervent tangle]

so keep both examples?

[leaden swan]

Why induct

[fervent tangle]

i'm not sure if it is induction tbh

[verbal axle]

its not

its a direct proof

[fervent tangle]

the general case of i should suffice

so will i need the examples?

[verbal axle]

it will suffice

[fervent tangle]

okay thx

[verbal axle]

this is what the proof looks like in my class notes lmao

[fervent tangle]

XD

[fervent tangle]

what year is that course for?

the one i am taking (cuz of joint honors) in 2nd year is for first years and contains a introductory mix of number theory combinatorics and algebra

so i think they just make the proofs like that for ease

[verbal axle]

this one is for 3rd years (i think)

the courses at my school are very difficult to assess for a year thing

Im taking this in first year tho

[verbal axle]

like linear algebra 1 is labelled as a 2nd year course, if we go by course code, but its a required course in 1st year

[fervent tangle]

the courses are quite a mess in my uni

in my degree we are required to do 2 years of analysis but we aren't allowed to take any analysis modules for the rest of the degree

whereas you can do every combinatorics and optimization module after 1 course in the 2nd year

[verbal axle]

to finish my program I have to take an additional year, so thats gonna be fun lmao

[fervent tangle]

[verbal axle]

I dont have to pay much, luckily, so I'm fine

[rapid glen]

anyone can find the 4 last digits of 2^2016

[errant otter]

use modulo
What are your workings so far?

[spring pier]

What

How did you get that lol

Okay but how do you know that 2^2000 is congruent to 1 mod 10000

[spring pier]

Tbh I'd use Chinese remainder theorem

[errant otter]

Oh, you could use CRT to solve this?

[rapid glen]

what are the steps

[spring pier]

Factor 10000 as 2^4 5^4 and it's a bit finicky but i think it would workc

[errant otter]

ahhhh

[rapid glen]

but what then

[rapid glen]

can you explain what i do now

[spring pier]

Do you know what the Chinese remainder theorem is?

The idea is non trivial but

You'll get a congruence 2^2016 = x (mod 5^4)

And the way to solve this is to first solve it mod 5 and the life to solutions mod 5^4

From this then you'll be able to use the Chinese remainder theorem again to get back ur original solution

Double take on that lifting thing

You can just use Euler's theorem

[rapid glen]

can you help me with it

[upper venture]

any1 good with diophantine eq?

not sure if i did this right

[verbal axle]

have you done a) ?

[runic token]

what book is that

that's such good notation for mods

i like that

[verbal cedar]

yeah i've been using it for a while. it's sooo compact it's great

[surreal crescent]

solution without brute force (look at last edit) came out

can u explain this though

i have no idea whats going on

[smoky patio]

how does those integers being composite, it follows that primes have arbitrary large gaps. does

how does it follow

ahhhh

nevermind i understand now, because the composite numbers can have arbitrary length of k, so primes have arbitrary gaps of k

[blazing ferry]

hey, i saw in a michael penn video that you can expand the meaning of unit, prime and composite to just be unit: has a multiplicative inverse, prime: ab = p --> a=p or 1, b=1 or p, composite is anything else
does that mean that when we are working with rational numbers there are no "primes"? or am i really misunderstanding

[plucky jacinth]

0 is actually a prime in the rationals (and in the integers)

0 is the only prime in the rational numbers

[leaden swan]

0 is not a prime

[plucky jacinth]

(0) is certainly a prime ideal

In an integral domain

[leaden swan]

Well Z/(0) is not an integral domain

[plucky jacinth]

It definitely is

It's just Z

[leaden swan]

Ah my stupidity

[plucky jacinth]

Usually one excludes 1 from being a prime even though R/(1) is always an integral domain though

[still flare]

0 is usually excluded from being a prime when we talk about things like UFDs because that would break unique factorisation :) similarly for 1 being a prime

[normal heart]

I think (0) is usually allowed to be a prime ideal in integral domains, but 0 is usually not classified as a prime

[still flare]

This is my experience as well

[unkempt void]

I can't imagine not allowing (0) to be prime in an integral domain lol

[unkempt void]

Iirc aren't integral domains nonzero by definition anyway?

[still flare]

Well this is what excludes the whole ring from being a prime :)

(prime ideal, I mean)

[simple thorn]

idr what the problem was but there was this problem that went something like “Can you produce a set of positive integers of arbitrary (finite) cardinality that satisfies property x” and the answer was the construction {n! + 1, n! + 2, … , n! + (n - 1)}. Would anybody have an idea what the problem is

[wooden glen]

Find so-and-so many consecutive integers none of which are prime.

[simple thorn]

Ohh I think it was n consecutive compositez

yeahhhh

thanks

[runic token]

this is not the right construction btw

i'm being a little pendantic

but

n!+1 can be prime

you'd want to instead start out with n!+2 and end with n!+n

[simple thorn]

oh right 1 being a divisor of n!+1 is not very helpful

[normal heart]

1 is a divisor of every integer...

The issue is you can't guarantee n!+1 being composite, say 3!+1=7

[verbal cedar]

11!+1 is also prime iirc

[torn escarp]

https://oeis.org/A088332
just calculated some and looked it up on oeis
1!+1 = 2
2!+1 = 3
3!+1 = 7
11!+1 = 39916801
27!+1 = 10888869450418352160768000001
37!+1 = 13763753091226345046315979581580902400000001
41!+1 = 33452526613163807108170062053440751665152000000001
73!+1 = 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000001
77!+1 = 145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000001

interesting, it's like a short-circuited version of wilson's theorem since n!+1=p means n! = -1 mod p with n<p-1

does this happen infinitely often?

we can actually say a couple things

since n! = -1 mod p and (p-1)!/n! = -1 mod p that means those two disjoint products of integers in {1,2,...,p-1} must contain roots of -1

is that enough to say p=1 mod 4 for this to occur?

(for n sufficiently large)

oh duh of course p=1+n! lmao

[runic token]

is it possible to have two consecutive numbers where n!+1 and (n+1)!+1 are both prime besides 1,2,3

if so, does this happen infinitely often

[torn escarp]

that sounds tractable hmm

[leaden swan]

n=2

[torn escarp]

I was collecting data on how often for 1 <= n <= p-1 that n! = -1 mod p for each p, since I got side tracked wondering about how often wilson's theorem "short circuits" to -1 early

[leaden swan]

that feels like the only solution

Looking at exisiting factorial primes

[torn escarp]

probably not that useful but it would mean $p_{n+1}=n*n! + p_n$

[sterile pumice]

Merosity

[torn escarp]

the n subscript means $p_n=n!+1$ not the nth prime

[sterile pumice]

Merosity

[errant otter]

I think this is quite similar to the proof that there're infinitely many primes...

[runic token]

yes!

good insight!

[errant otter]

since you can generate primes (albeit not in order) by multiplying whatever primes you want to start with and adding 1

[runic token]

another fun fact: kmm

did you know

[errant otter]

it's been mentioned?

oh

[runic token]

that euclid's original proof of the infinitude of primes

[errant otter]

mb

[runic token]

is not actually by contradiction

[leaden swan]

Hmm I think n!+1 is prime => n is prime

[errant otter]

induction?

[runic token]

hmm no

[runic token]

huhhh for some reason i doubt this

[errant otter]

this time instead of just multiplying primes, we also multiply all preceding numbers

so it raises the qn if it will be prime

[torn escarp]

yeah, it's not necessarily a prime, I think that's a common misconception people have about the proof though that (prod of finite collection of primes) + 1 is prime

[runic token]

bc we can consider mods, no? and even if composite i don't think there's any reason it can't be prime

[runic token]

@leaden swan 77 isnt prime

[leaden swan]

Ah mb

[runic token]

ur good i didnt notice that either 😭

oh

so is 27

silly me

[leaden swan]

Why is that not mentioned here then
https://en.m.wikipedia.org/wiki/Factorial_prime

[torn escarp]

nice, progress

[torn escarp]

also better version of this that just tracks n not p: https://oeis.org/A002981

[errant otter]

stonks

[runic token]

oh

bad news

[runic token]

open question apparently

https://t5k.org/glossary/page.php?sort=FactorialPrime#:~:text=It is conjectured that there,and 26951 (107707 digits).

[torn escarp]

not surpising I guess

[torn escarp]

that's why I diverted to doing this instead haha

[runic token]

oh right right

is wilson's thm the

[errant otter]

open questions we go again

[runic token]

(p-1)! = 0 mod(p)?

[errant otter]

-1

not 0

[runic token]

oh pf ur right that was silly

[torn escarp]

first column is p, second column is how many n<p such that n! = -1 mod p
2 1
3 1
5 1
7 2
11 2
13 1
17 1
19 2
23 3
29 2
31 1
37 1
41 1
43 2
47 2
53 1
59 4
61 4
67 3
71 7
73 1
79 4
83 4
89 1
97 1

[errant otter]

Green leaf spam in chat!!

[torn escarp]

71 jumps to 7 but otherwise they stay pretty low

[errant otter]

[torn escarp]

lol

[runic token]

hmmmmmmmmmmmmmmmmmmmmmmmmmmm

[errant otter]

sus

[runic token]

interesting

[torn escarp]

up to 5,000

[runic token]

it doesn't even look like the proportion of numbers is going up very quickly

[errant otter]

wtf

how the hell u guys pulling these outta nowhere

[torn escarp]

weird thing is these just stay at about 1 to 4 even up to 5,000

[runic token]

3643 is 8

[torn escarp]

I wrote a little loop to mkae this list

[runic token]

which is the highest i've seen

[errant otter]

mero using code

[torn escarp]

8 3643
8 3643
7 71
7 661
7 4241
7 4241
7 3541
7 3541
7 3163
7 3163

weird idk why those are appearing twice

8 3643
7 71
7 661
7 4241
7 3541
7 3163
7 2267
6 4663
6 4591
6 4259

[runic token]

interesting

this does seem to almost confirm

that as it gets higher

[errant otter]

bruh number theory be wilding

[torn escarp]

I think I appended the data twice and accidentally reran it

[runic token]

the numbers are too

but ig this could also just be

bc we have more numbers

[torn escarp]

it's weird how slow it grows

[runic token]

slow growing hierarchy be like

[torn escarp]

plus the top 3 are actually like pretty small by comparison to the rest there

[runic token]

that's true

run it further i wanna see

what's the code btw?

[torn escarp]

doing that now, takes a while

[runic token]

are you just

[errant otter]

this is rlly sus
well who am I kidding NT is super sus

ok wait

[runic token]

running the thm

for every prime

[errant otter]

this is gonna be embarrassing but
what is this supposed to compute

[torn escarp]

f=fileopen("wilson_short", "a"); forprime(p=5000,6000, w=1; for(n=2,p-2, if(Mod(n!,p)==-1, w++)); filewrite(f, strprintf("%d\t%d", p, w))); fileclose(f)

in pari-gp

[errant otter]

[torn escarp]

just finished 5-6k

[runic token]

@errant otter

[errant otter]

.........

I'm blind

ok gotcha

[torn escarp]

8 3643
7 71
7 661
7 5503
7 4241
7 3541
7 3163
7 2267
6 5791
6 5051

updated leaderboard

[runic token]

three changes

hm

but

still

this is almost funnily slow growing

[torn escarp]

yeah 71 and 661 are sorta strange

like even 3643

[runic token]

what's special abt those numbers

[torn escarp]

the max just seems to pop out really early as outliers

[errant otter]

wait so what's the increase? I wonder if we compared all the numbers, we may/may not be able to find a pattern

[torn escarp]

8 6529
8 3643
7 71
7 661
7 6359
7 6043
7 5503
7 4241
7 3541
7 3163

[runic token]

i think it's gonna be a lot more numerical data needed

until we can find a pattern

[errant otter]

ydeah...

[runic token]

oooooh

new 8

[errant otter]

nani

[torn escarp]

it's starting to take a while to compute

[errant otter]

XD expected

[torn escarp]

I might not get to 10K

[errant otter]

smh use C++

[runic token]

are there any more efficient ways to calculate wilson's thm

[errant otter]

[torn escarp]

you use C++

[errant otter]

shit I've been exposed of not knowing how to use C++

[torn escarp]

I think gp really is just taking this and using the pari C library behind the scenes anyways

I don't really know anything about C or what it'd take to optimize code for this, never really cared to do that sort of thing lol

no updates up to 7k

in the top 10

[runic token]

i will write code for this in python when i learn it

which should theoretically run faster

[torn escarp]

or sorry up to 8k

[errant otter]

well

it would if u use numpy

ig I could give it a shot

[runic token]

do it kmm

[torn escarp]

if you look on project euler at the most used language, it's pari-gp haha

[errant otter]

crap

here I go again

[runic token]

ur putting off the integrals i gave you anyways

[torn escarp]

it's pretty optimized for doing number theory calculations as far as I know

[runic token]

hmmm

that's probably true

[torn escarp]

8 6529
8 3643
7 71
7 661
7 6359
7 6043
7 5503
7 4241
7 3541
7 3163
7 2267
6 8863
6 5791
6 5051
6 4663
6 4591
6 4259
6 401
6 3947
6 3581

[runic token]

makes me wonder if there's a more efficient way to compute this

still only two eights damn

[torn escarp]

ok only 1K more til 10K

[runic token]

and 71 is very silly

[torn escarp]

the RHS is not really "sorted"

like they're all 7s there so it us thappened to be first basically

[runic token]

yeah but 71 and 661 seem very low

[torn escarp]

yeah true

I'm sort of thinking about it from a group theory perspective

is there a reason we should expect it to be so tiny like this

it's sorta like taking random elements of the group and multiplying together and hoping you make -1

more specifically, if I give you a cyclic group, and you take out elements one by one without replacement uniformly randomly, and multiply them, how often would you expect to make -1?