elementary-number-theory

[iron surge]

that's the thing....I'm not seeing an example.....

[whole bronze]

Just for the part glossed over

[iron surge]

the minimality of r part

ahh so we're agreeing after all lollll

yes it's glossed over

yes it needs way more elaboration

100% agree

[whole bronze]

I wouldn't call it a proof if it has a part like that

It may not even be able to be filled

[iron surge]

it makes sense to me why it's true, but yea it's not good if it's not convincing to others

[whole bronze]

Or you'll have to restructure the rest of the argument to actually make it work

[whole bronze]

Well not really that it's not convincing more that it's not deductive

It doesn't follow from simpler assumptions and pure logic

Which is what proofs are

[iron surge]

all I need to elaborate on is why such an r is desirable.. that's literally all that's missing

everything else is fine

[whole bronze]

Something being convincing or making sense isn't a proof which a sequence of logical deductions from a base set of assumptions and axioms

[normal heart]

it's fine apart from a small elaboration

it's a standard argument anyway

[iron surge]

assumptions good, construction of S good, well-ordering principle good, r good, conclusion pretty jumpy

[iron surge]

thank u

yes

@whole bronze I was tryna help u see this problem in another light lol not debate about the semantics of logic......

[whole bronze]

If there exists a subproof then yes - if there is not then the argument would need to be restructured

[iron surge]

the argument is fine lol, even someone else agreed, just needs added details so readers can understand it better.....

I'll think about this problem some more

and why such an r is fine

i do agree extra details would be good for sure

[iron surge]

I got something

wait nvm

[whole bronze]

What's the standard argument?

Add them all together to get sum of xi then subtract consecutive rows probably

[spiral coyote]

Hi! I want to study elementary number theory because of a contest, but I cannot find questions to start with. Does anyone has a resource which contains many questions related to elementary number theory? Thanks in advance!

[sullen mist]

Hi, is this proof correct, if m does not divide a, and m does not divide b show that m does not divide ab

[still flare]

The statement is false so without looking at your proof I can tell you it's wrong.

[sullen mist]

is it possible to look at it and tell me where I went wrong?

[still flare]

Yes, r_1r_2 is indeed nonzero but you need in fact to prove that r_1r_2 is not divisible by m, not that it is nonzero.

[sullen mist]

just started learning number theory and proof math

ah I see

so m might divide ab or it might not depending on a, b and m, hence nothing to prove?

[still flare]

What do you mean, nothing to prove? You haven't yet proven it's false.

To do so you must find a counterexample

[sullen mist]

got it e.g. a = 2 b = 3 and m = 6

[still flare]

Good job, that's the one I had in mind too.

[sullen mist]

went that route because I was trying to show that gcd(n, p^k) = 1 when p is prime, k > 0 and p does not divide n

the book says this is obvious, but not obvious to me

[still flare]

This is obvious by the definition of the gcd: it is a common divisor of both n and p^k. The only divisors of p^k are powers of p, and there are no powers of p which divide n.

[sullen mist]

I think it's not obvious to me that the only divisors of p^k are powers of p

but maybe it's a direct consequence of prime factorization

oh I think I get it

fundamental theory of arithmetic says the prime factorization is unique

p^k = p.p.p.p... k times

since unique we can't have any other factorization, hence only divisors are powers of p like you said

and since you can't find p in n you can't find any multiple of p in n without remainder

thanks @still flare

[wooden glen]

Note that this would become true if you added an assumption that m is prime. (Namely, then the claim would just be the contrapositive form of Euclid's lemma). And that may well be all you actually needed for the purpose you stated later.

[sterile pumice]

gian

[dusty dragon]

showing that the statement works for one value of a, b, c is not a proof

the statement is true when a is prime, so consider what happens when a is not prime

[iron surge]

yea you only showed it's true for your example. This problem says if a is a factor of bc, then a is a factor of b or a is a factor of c. think about a case where bc yields a product that could equal a, but b=c are half of a.

[sacred junco]

I did not write this proof. The point of the problem was to point out why it’s incorrect

[iron surge]

so you didn't write "Proof: Let a=5...?"

[sacred junco]

No

That was all apart of the problem

[iron surge]

ok

[sacred junco]

It was basically like a proofreading assignment

[iron surge]

ok lol. Well proof by examples aren't considered proofs unless there are only finitely many cases and if all cases have been covered

that's the problem with the proof

[sacred junco]

Ohhh okay I did not know that

[iron surge]

and also for showing the theorem is false....it is fine to show one counter-example

that is all u need to show the statement is false

[sacred junco]

I see

I'll send my "solution" to the problem in a second let me just format it

[iron surge]

the "theorem" states: You give me any integers a,b, and c, and if a|bc, then a|b or a|c

[sterile pumice]

gian

[sacred junco]

Hopefully that makes sense

[iron surge]

this is very wrong

[sacred junco]

lOL

[iron surge]

if a|(b+c), does that really mean a|b or a|c?

I don't think so

take

2|4=1+3

2 doesn't divide 1 and 2 doesn't divide 3

so the statement you stated in ur proof isn't true

[iron surge]

also if even if it was a true statement, u assumed the very thing ur trying to prove! You went and assumed a|b and a|c on the second line of the proof!

[sacred junco]

Eesh I got a lot of learning to do

[iron surge]

you also didn't even prove the statement. You proved the converse of the statement...which is actually true

[iron surge]

also your counterexample for theorem 1 isn't a counterexample at all

you stated let a=4 and b=3 and c=10....10 doesn't divide a or b. But that doesn't even matter because 10 doesn't divide their product in the first place!

10 doesn't divide 12

and when you're writing a counterexample to theorem1, use the letters they used in the order they used them

ur "counterexample" was for "if" c|ab (which wasn't the case) when theorem 1 was a|bc...make it easier on the reader.

[sacred junco]

ok ill see what i can muster up and hopefully it makes more sense

@iron surge

How is this any different from what I wrote

[iron surge]

look at what you stated as your "theorem" just above ur proof

[sacred junco]

oh

[iron surge]

here^

[sacred junco]

mines backwards

[iron surge]

yea

so it's very different

[iron surge]

this proof^ here is good

[sacred junco]

i found that online

[iron surge]

of course ❌

have you found a counterexample to theorem1 yet?

the one you originally asked about

[sacred junco]

uhhh no let me try again

i think the counterexample to theorem1 fails if a=6, b=3, and c=10

[iron surge]

show it fails

[sacred junco]

one sec let me type it up

let $a=6$, $b=3$, and $c=10$. Then $a|bc = 6|30$ \
\
$\implies 30=6s$ which is true for s=5 \
\
$a|b = 6|3 \implies 3 = 6t$ which is not true for $t \in \mathbb{Z}$\
\
$a|c = 6|10 \implies 10 = 6v$ which is not true for $v \in \mathbb{Z}$

[sterile pumice]

gian

[sacred junco]

how does that look

[iron surge]

I like the a|bc part. 6|30 because 6(5)=30, that's fine

but

technically u should say and u sorta did but

say

$6\nmid 3$ and $6\nmid 10$

[sterile pumice]

logician

[iron surge]

it's just awkward because you wrote a|b=6|3, which isn't true

and weird notation

[iron surge]

just say this instead^

[sacred junco]

i get what you're saying

it was useless to add that

i kinda did the same thing for a|bc = 6|30

[iron surge]

I would say: Set $a=4$ and $b=c=2$. Then $a=4|4=(2)(2)=bc$, however, $4\nmid 2$. Thus $a\nmid b$ and $a\nmid c$.

[sterile pumice]

logician

[iron surge]

that part was fine for a|bc

[sacred junco]

OH i see what you're saying

[iron surge]

also my counterexample is a bit simpler, though ur values for a,b,c work just as well

[sacred junco]

damn this stuff is tough

thanks for your help

[iron surge]

no problem. I'm gonna get some sleep now

[undone elm]

Hello everyone, just a really short question.
The set ${0,1}^\mathbb{N}$ how should I interpret this.
Can I interpret this as all infinite strings consisting of 0 and 1's, or is it just any string consiting of 0 and 1's (so also including finite ones)

[sterile pumice]

yesyesufcurs

[eternal shoal]

That would be all infinite strings if you want to think of it that way. But this isn't elem NT

[undone elm]

Sorry I must be blind that I posted it here 😅 But thanks for the answer!

[loud maple]

Shouldn't it be the set of all countably infinite strings of 0s and 1s?

[open mist]

It's the set of sequences whose value is 0 or 1

[loud maple]

Set of sequences with domain ℕ whose value is 0 or 1

[eternal shoal]

(by definition a sequence has domain N)

[loud maple]

No

A sequence is any function whose domain is an ordinal

At least that's the definition we used in my set theory course

[eternal shoal]

I would say from what I've seen, a sequence is a function with domain N unless specified otherwise. I've seen non-N indexed sequences specified as, say, transfinite or λ-sequences for an ordinal λ, but admittedly I have not taken a set theory course.

But anyways, their question had that the domain was N implied by the notation {0,1}^N. So replace that with N/ω-sequences as you wish.

[frozen patio]

hey guys, can someone here proofread my notes on euclid's algorithm/bezout lemma?

i'm mostly interested in flaws and ugly points in my proof

[charred roost]

It looks correct to me. I like to write the remainders a - d_1 * b = r_1, because it makes it obvious to me that since the left side is divisible by the GCD, the remainder also must be

[charred roost]

If you're interested, I wrote a blogpost about this: https://blog.sheddow.xyz/gcd-euclid-and-bezout/ You probably know most of it already, but check out the animations 🙂

[whole bronze]

given an odd prime p, listing the values of a^((p-1)/2) for different values of a nonzero mod p will always have half the values of a give 1 and the other half give -1
if you replace p with the number x = 8 though, you see that in the group of elements relatively prime to eight a^(phi(x)/2)=1 for every a
1^2 = 1 mod 8
3^2= 1 mod 8
5^2 = 1 mod 8
7^2 = 1 mod 8
why is this?

[brittle root]

those elements are all of order 2 lol

U(8) is isomorphic to Z_2 x Z_2

[whole bronze]

I was asking more about why half of them weren't -1 mainly because degree two polynomials should have two roots

I realize I am dumb now because that is not a field

[brittle root]

er

[whole bronze]

Also found carmichael's function

[brittle root]

degree n polynomials over a field have at MOST n roots

doesn't mean they have n roots yeah

[whole bronze]

Right at most

[whole bronze]

But carmichael's function/when things have primitive roots is probably something I'll have to read on my own to understand

[frozen patio]

thanks!

I know about that stuff but I am revisiting the fundamentals trying to prove the more important results, so thanks for the link too!

in retrospect it seems obvious that all those riddles with the containers of different volumes had to do with the gcd

[steep cobalt]

Hi. Speaking of gcd. I’m trying to find the gcd of 213,34 and I got two. But when I check online it said one. I understand why it’s obviously one and I got to the bottom, but I’m not sure why in terms of showing my work

[loud maple]

gcd(2,1)=1

[loud maple]

Also don't use the '=' sign between every consecutive calculation step

[steep cobalt]

So on my paper, is the gcd the number in the parenthesis and the zero?

Just for reference if I do this again but with a different number

[loud maple]

Going by the convention you used in previous steps, your last step should have 2 = 1(2)+0

[steep cobalt]

Oooh ok

Ty

[little heron]

How do I prove the division algorithm, how do I show the least element of a set equals something (new to proofs)

[iron surge]

by constructing a set wisely upon which you will apply the Well-Ordering Principle to.

[white lion]

why are you giving him the impression that he even has a chance to prove the division algo on his own without even a lot of math experience

[iron surge]

Why are you assuming it's out his reach? Never underestimate how smart someone may be. I'm simply giving him somewhat of a hint without actually spelling out every detail of what he needs to do. This is because 1.) He hasn't posted anything that shows he's even attempted the problem. and 2.) Some people just want really small hints and don't want to be spoon-fed the whole proof! He will feel much better getting the proof down with little help than with a lot of help.

@little heron Ping me if you want more hints

[white lion]

Well he said he was new to proofs and you are giving him the impression he could solve it might waste a lot of his time

Reading and understanding the proof is would be much more beneficial at this time for unknown

I know you’re trying to help but

[iron surge]

I'm simply giving him the impression that he can do this with some help and that help can be very little help! Stop putting this past him and besides...let's leave "what impression" I'm giving him up to him to interpret. You weren't even the one asking the question he was asking, so there's no good reason for you to get involved. You aren't even helping anyways. I don't see you posting anything that replies to his question. You're just complaining about me, the one, person who's replied to him in the 3+ hours after he posted his question.

[little heron]

if I have a specific set like {1,2,3,4} 1 would be the least element in this particular set right? If that's true, how do I relate that with r the remainder in the division algorithm

[iron surge]

yes. Notice that we need r to be nonnegative and the WOP works perfectly for nonnegative integer sets.

[white lion]

Btw Proving the division algo requires using cases and creating such a set that everything works properly, not that difficult if you have some experience in elementary number theory but waste of time for a beginner

[iron surge]

jayz

how is that helpful info for him?

[white lion]

yeah

[iron surge]

pls stop, he's asking me questions

[little heron]

I still wanna learn how to prove A is a proper subset of B too I know A has to be a subset of B and A≠B but that's about it

[white lion]

go ahead 🙄

[iron surge]

You show A is a subset of B by showing "If x lies in A, then it lies in B." You show proper subset by showing there is something in B not in A

Recall, for the division algorithm, you must show that given an integer a and an integer b, there are unique integers q and r, such that a=qb+r and 0<=r<|b|

so construct a set like this:

[little heron]

if I had like A={2,3} and B={2,3,9} then would A be a subset of B in this case just trying to make sure

[iron surge]

yes because everything in A is in B

it's a proper subset because also 9 is not in A

but is in B

[little heron]

But the reverse isn't true B isn't a subset of A right

[iron surge]

Right

Two sets are subsets of each other exactly when they are equal

[iron surge]

$S={a-xb: x\in\mathbb Z,\ a-xb\geq0}$

[sterile pumice]

logician

[little heron]

I also know that the empty set is the subset of any set and a set is a subset of itself but that's the extent I've learned on my own

[white lion]

Unknown who’s asking you to prove the division algorithm? Just curious

[little heron]

No one

[iron surge]

oh god jayz

[white lion]

Is it an excercise?

[iron surge]

he's just tryna learn proofs man

[white lion]

I’m just curious!

[little heron]

I'm following a YouTube video for context

I still need more practice on sets

[iron surge]

let his mathematical mind wander

/wonder too

[little heron]

The one that gets confusing is the " summation like" notation for intersections and unions

[little heron]

In this part I wouldve put x>0 but why put the entire expression

[iron surge]

x>0 doesn't guarantee x is an integer

so I need that x is an integer

and that a-xb>=0

so then a-xb is a nonnegative integer

which is what we require of r

[little heron]

Is that from following the inequality of the statement

[iron surge]

yes a-xb>=0 means a-xb is nonnegative

[iron surge]

look at r here^

it must be nonnegative as well

[little heron]

I know that r is between 0 and b

[iron surge]

yes

[iron surge]

rearranging a=qb+r from here gives a-qb=r

which is how I essentially constructed my set

[little heron]

I understand that part

[iron surge]

so now if this set is nonempty, then it must be a set of nonnegative integers. So we can apply the well-ordering principle if we show the set is nonempty

[little heron]

Would a-xb be considered an element of the set

[iron surge]

yes elements of S look exactly like that

by construction

[little heron]

So if a set is non empty it's the opposite of the empty set (no elements)

[iron surge]

opposite in the fact that it's nonempty and the empty set isn't. We typically say a set is nonempty instead of saying it's opposite the empty set

or we may say a set is nonempty by saying it has at least one element in it

[little heron]

Makes sense

The person in the YouTube video used random numbers for a and b and show there's a least element but could you do this without doing all that

[iron surge]

Now note that there are different versions of the division algorithm. Some with a and b as integers and some with a and b being both strictly positive integers with a>=b. For the sake of learning a proof, I recommend we do the strictly positive integer case

[little heron]

For now I just want to show a=bq+r and not the inequality

[iron surge]

random numbers works if a and b are given values that we know of like a=4 and b=2, but we want to prove this for all positive integers a and b so we must keep them arbitrary

[iron surge]

there are two parts to this proof: existence and uniqueness. The equality comes very soon as follows

So recall I'm doing for the case where a and b are positive integers with a>=b.

Then $a-(1)b\in S={a-xb: x\in\mathbb Z,\ a-xb\geq0}$ since $1\in\mathbb Z$ and $a\geq b$.

[little heron]

i wouldve read that as a is bigger than b

Or equal to

[iron surge]

yes

[sterile pumice]

logician

[little heron]

Why did you say a-1 where b is in S

[iron surge]

I wrote a-(1)b to get it in the form a-xb

I know a-(1)b=a-b

and that a-b is nonnegative since a>=b

so a-(1)b must be in S

[little heron]

What about a-x

[iron surge]

elements of S only look like a-x when |b|=1

look at how I constructed S. a and b are arbitrary but fixed, so I need to show that there is some integer k for which a-kb is nonnegative and therefore is in S

[little heron]

For the first sentence, are you saying (a-b) is in S

[iron surge]

here^ yes

a-b=a-(1)b is in S

[little heron]

kind of unrelated but if a divides b then b=ka where k is an integer something along those lines reminded me of this

[iron surge]

yes and in that case. If a divides b, then a=kb+0 for some integer k. 0 is the remainder in that case

this is why we allow r to be nonnegative and not strictly positive

[little heron]

Is non negative the ≥

[iron surge]

yes a-b>=0 means a-b is nonnegative. And notice a-b>=0 is the same as saying a>=b

[little heron]

To be honest this is a little advanced for me I think I need more practice with sets and set builder notation

[iron surge]

alright sounds good.

[little heron]

I did learn this one though

odd number={2k+1 | where k is an integr}

[iron surge]

I appreciate the curiousity in this topic!

[iron surge]

yup and the set of even numbers is {2x:x is an integer}

the set of even integers is often denoted by $2\mathbb Z$

[sterile pumice]

logician

[little heron]

Might sound greedy here, but could you quiz me on basics of the basics of sets if you have time

[iron surge]

sure! could I possibly quiz you tomorrow. I need some time to come up with a fairly comprehensive quiz than just a couple problems I can come up with off the top of my head

[little heron]

It doesn't have to be really comprehensive I am a beginner afterall

[iron surge]

it would also be good practice for you to be quizzed by other people in the discrete math channel since there is more than one way to define the same set and being exposed to the different notation can be quite useful

K give me about 10mins

[little heron]

I also know the upside down A is for all and weird looking E is there exists its a really unique symbol

[iron surge]

ah are u familiar with those symbols and how they are used?

I would be much better at quizzing you on that than set theory since I'm way more versed in logic than set theory!

[little heron]

Not too familiar but I know a little bit

I did memorize some of this one

"all epsilon greater than 0, there exists a delta greater than 0 such that..."I forgot the other stuff in detail

For limits

[iron surge]

gotcha gotcha.

[little heron]

Also I watch a lot of Michael penn so kind of learned some stuff from him

[iron surge]

So if I say, for all integers k, there exists an integer n such that n>k. determine if that's true and see if you can prove it is!

[little heron]

Is this how you write it

Kind of a dumb question but is 0 considered an integer

[iron surge]

yes

0 is an integer yes

[little heron]

if n, k are integers and n>k then n-k>0 but id get stuck there

An Idea I have is either n is odd and k is even

2k+1 definitely seems bigger than 2k

[iron surge]

So my statement says that you give me any integer k and I can find another integer n greater than k

[iron surge]

the problem here^

[iron surge]

and here^ is that really we don't need to be concerned with when n is odd or even

if anything, it would be for when k is odd or even

but I'd argue we don't even need to know if k is odd or even

I'm going to prove the statement so you can see how a proof for this statement works

\begin{proof}Given an integer $k$, choose $n=k+1\in\mathbb Z$. Then $n=k+1>k$.\end{proof}

[sterile pumice]

logician

[iron surge]

this is the proof for the statement: For any integer k, there exists an integer n, such that n>k

[little heron]

You could also n=k+2 too

[iron surge]

that is also the same as saying: For any integer k, n>k for some integer n.

[little heron]

And so on

[iron surge]

yup! infinitely many choices

for n

[little heron]

That was a tricky one

[iron surge]

Alright now let's see here. I'm going to give you a nested quantified statement (so using more than one quantifier as before) and I want you to write it into formal logic.

Translate Definition 2.1 here into formal logic using predicate logic

[little heron]

I can't use words right

[iron surge]

right. Just translate the part from "for every..." up to "...< e"

[little heron]

I tried my best

[iron surge]

good except $\forall x\in\mathbb N$ should be $\forall \epsilon>0$

[sterile pumice]

logician

[iron surge]

positive number in this context means positive real number...not necessarily positive integers.

[little heron]

I see that mistake

[iron surge]

of course if this is true for every positive real number, it is true for every positive integer

but yea technically the definition is talking about epsilon being a positive real number

nice job

sometimes this definition is also stated like this:

For any $\epsilon>0$, there is a natural number $N$ such that $|a_n-a|<\epsilon$ for all $n\geq N$.

[sterile pumice]

logician

[iron surge]

just like how "For any integer k, there is an integer n such that n>k." is the same as "For any integer k, n>k for some integer n."

[little heron]

I like the first version better for some reason it's more chronological in my eyes

[iron surge]

yes me too

easier to digest

Read how the definition is defined in this pdf^

[little heron]

I remembered this one as well

[iron surge]

yes that is the cartesian product of RxR

[little heron]

If I have a function x^2 is that in R^2 since it's 2d ish

[iron surge]

Yes if, for example, you define f as follows:

Define the function $f:\mathbb R\rightarrow\mathbb R$ by the rule $f(x)=x^2$ for all $x\in\mathbb R$.

[sterile pumice]

logician

[iron surge]

now technically x^2 is not in R^2

since x^2 is a single point in R

and not an ordered pair

however (x,x^2) is in R^2

[little heron]

Makes sense

[iron surge]

when graphing this function, we use this^

[little heron]

Does this look correct I made up the example

[iron surge]

yup looks good. don't for get the squigly brackets on the right side too to close the Power set of A

[little heron]

i also learned 2^(cardinality of A) = cardinality of power set

[iron surge]

And you know that's all the subsets of A because there are 2^3 distinct subsets of A and you listed 8 subsets of A that were all distinct. So there's no subsets that you're missing.

[iron surge]

yup was just typing that when you said it

[little heron]

I think I'd rather be quizzed on basics sets problems like these than proofs for now

Im not at that level yet

[iron surge]

okay

Let $A={a,b,c,d}$ and $B={b,d,f}$. Determine if $A\subseteq B$, $B \subseteq A$, and determine $A\setminus B$, $B-A$, $A\cup B$, and $A\cap B$.

[sterile pumice]

logician

[little heron]

Didn't have enough space

[iron surge]

looks good so far

[iron surge]

For these same sets $A$ and $B$, if $C={a,b,c,d,e,f}$, determine $\overline A$ and $B^c$.

[sterile pumice]

logician

[iron surge]

perfect!

[little heron]

To be honest don't know up until that point

[iron surge]

this is asking what A complement and B complement are

A complement is the things not in A (but in C)

B complement is the things not in B (but in C)

[little heron]

For the first one would it be {e, f}

[iron surge]

C is the universal set in this case, otherwise A complement would be a whole slew of infinitely many random things

[little heron]

B complement={a, c, e}

[iron surge]

perfect

yup so $\overline A={e,f}$ and $B^c={a,c,e}$ as you pointed out.

[sterile pumice]

logician

[iron surge]

those are two different ways of writing set complements

$\overline A=A^c$

[sterile pumice]

logician

[iron surge]

and so of course $\overline B=B^c$

[sterile pumice]

logician

[iron surge]

different texts use different notation

[little heron]

I saw a video once and the univeral set is denoted as U , would the problem have to tell you if C is a universal set

[iron surge]

technically yes, it should

[iron surge]

so here^ technically I should've stated C is the universal set for this problem. Obviously A and B are subsets of C, but saying C is the universal set is the way you know the universe isn't any larger than C.

good catch

[little heron]

Based off what I did do I know some of the basics atleast for sets

[iron surge]

I'm gonna head off to bed, great work on these problems. BTW the division algorithm question was posted in the correct channel (here in the elementary number theory channel). Set theory questions, should go to the discrete math channel.

[iron surge]

I would say so yes. We didn't cover partitions in my quiz yet, but so far looks good!

[little heron]

When are you usually online

I'm free all day tomorrow I love doing these problems

[iron surge]

Usually around 6pm PST onwards. But sometimes other things like hw and hanging out with friends changes that, but yea usually those are the times.

You can always ask someone in the discrete math channel too. There's lots of great people here some of whom are graduates and even PhD students!

nice working with ya Imma sleep now

[little heron]

Alright, good night, thank you for answering my questions means alot

[iron surge]

no problem thanks for the interests in the division algorithm! Even though the proof is not quite in your reach right now, I wouldn't say it's too far out of ur reach! Always good to have some sort of motivational problem you're working towards.

[charred roost]

Here's a pretty good quiz on sets: http://scherk.pbworks.com/w/page/14864241/Quiz%3A Sets

[steep cobalt]

Hi. So the class this is in is discrete math but i feel like this question fits here. Any help will be appreciated.

i can give a snipit of the textbook for more context. I tried to go to the textbook first but im still not too sure how to solve this

[white lion]

Ok so what would be the last term of the sum?

[steep cobalt]

I'm not too sure. If i was working with one variable I think i would be able to figure it out

[charred roost]

Try to write the sigma notation as a normal sum with ellipsis like: a1 + a2 + ... + am

[little heron]

I don't know if it's 6pm PST but if you could reply to this when you are online that'd be great

[white lion]

It is one variable, m is an arbitrary constant.

[steep cobalt]

I got it. Thank u guys

[white lion]

You can ask your question anyways there might be someone here that would help you

[little heron]

It's not a question, it's just I wanna be mini quizzed on basics of sets

Like yesterday

[white lion]

I’m not saying you’re not welcomed to ask here, but I think what might be a good path is to just pick up a book read and do the excercises

Elementary set theory shows up in almost all subjects in Math basically and many books have them in the introduction

Especially analysis topics like probability theory, real and complex e.t.c

And if you have issues trying to solve a question post it here

Well not here but #discrete-math

[loud maple]

Check out 'The Foundations of Mathematics' by Kenneth Kunen.

[little heron]

It looks too advanced

Im just learning this as a hobby

Because it's mildly interesting

[loud maple]

Ah ok

[little heron]

Like here I was being quizzed yesterday

I was genuinely learning

[scenic edge]

Imho solving exercise-sheets is kinda like the book author quizzing you. You just need to find the right book for yourself.

Are you particularly interested in set theory or there's other stuff?

https://www.amazon.in/What-Name-This-Book-Recreational/dp/0486481980

'cause if it's not just set theory and you wanna like, just have fun and solve puzzles, this is one fun book

[prisma folio]

Perhaps what I asked in #proofs-and-logic might also fit here?

[civic pecan]

is there someone have any suggestion about learning number theory?like how to start or suggested books,such things

[fiery zenith]

#book-recommendations for books 😵‍💫

no idea if khan academy might have some elementary things. and if good

[civic pecan]

thanks

[foggy linden]

I think that "Elementary number theory" by David M. Burton might be a good start. I like the way he includes lore of famous mathematicians and how they arrived at their famous results. Moreover, it's aptly explicit and challenging for a beginner.

Anyway, can someone look at this proof that i'm doing? It doesn't seem sturdy. Also, i might be missing some simpler approach.

If a has order hk modulo n, then a^h has order k modulo n.

PROOF:
Let's say that order of a^h is r.
now, r|k.
that gives, k = qr
We already have,
a^{hr} = 1(1 mod n)
a^{hk/q} = 1(mod n)

Now, i argue that hk/q < hk for q > 1, which violates the definition of order. Thus, q has to be 1, which gives k = r.
Is this fine?

Consider "=" sign to be sign of congruence in the appropraite places, please.

[buoyant mason]

how about this for simpler approach?
a^(hk) = (a^h)^k = 1 mod n, so the order of a^h is <= k. if the order was say m with m < k then (a^h)^m = a^(hm) = 1 mod n, violating a has order hk

[foggy linden]

Ah. Yes, that indeed is simpler. I knew i was missing sth obvious.
Thank you.

[buoyant mason]

yep ^_^

[fervent grove]

the equation x^2 - 34y^2 = -1 has no integer solutions, but it does have solution modulo any integer
the only proofs of the fact that there are no integer solutions use some nontrivial theory (either of Pell equations or of continued fractions); is there a more direct proof?

[torn escarp]

I tried an approach where I broke it into 3 cases and only managed to prove 2 cases. I rephrase the problem as, suppose we have an integer solution x^2+z^2=34y^2. Then the aim is to show that if p|z then p|x and p|y.

case 1: p=2 or 17, then x=0 mod p, and since x, z are squared, a single p|34 means p|y.

The next two cases p != 2 or 17.
case 2: suppose 34 is not a quadratic residue: then x^2=34y^2 mod p has only the solution x=y=0 mod p.

case 3: suppose 34 is a QR: 🥲

I'll sleep on it and hope this gap can be filled in

tangentially related, I knew this calculator had a 'show steps' button but it ends up using continued fractions in it too https://www.alpertron.com.ar/QUAD.HTM

whoops, that case 3 is impossible to prove cause it's false, that'd prove there is an integer solution to the original equation lmao.

[fervent grove]

yeah I do think continued fractions is the right way to approach these sorts of Pell equations

but I was talking to a prof about perhaps including this example in class, and I suspect that he doesn't have the time to do continued fractions in class

[barren garden]

god i’m so bad at number theory

[eternal shoal]

Is there a question that goes with this?

[barren garden]

i can’t even the very simplest of it

if a,b are natural numbers, and d is the least natural number on the form ax+by where x,y are integers… i can’t even show d divides a

[radiant sundial]

I guess it is but a trivial case

[radiant sundial]

He was asking why b cant be 0

[normal heart]

If d doesn't divide a, then write a=qd-r where 0<r<d

multiply q to both sides of ax+by=d

[barren garden]

whaat

[eternal shoal]

perhaps it just did not load for me. But yeah you can't divide things by 0, so it makes no sense to ask about when b = 0.

[radiant sundial]

I told him that

but he told me "There is no division by 0. Like x|z is literally defined with the meaning "z is a product of x and some integer"
0 is indeed a product of 0 and any integer"

[radiant sundial]

also + r not - r

[eternal shoal]

Doesn't matter

You can just change q by +-1 and you'll get another r with 0 < r < d.

[normal heart]

I'm just too lazy to say multiply both x and y by -1 in the last step

[eternal shoal]

The point is that you'll want to make the substitution || qd = r + a ||.

[prisma nymph]

¯_(ツ)_/¯

[cerulean rivet]

Not really, I had to post the image here since I can't post images in #discussion :DDDD

[cerulean rivet]

Again though, the text makes no reference to a division algoritm. It specifically says "If a=bc, then b and c are divisors of a and we write b|a"

0=0c works for any c so this fits the given definition of a divisor

I am not arguing for division by zero, I was asking about the convention choice that was made

but I've come to my own conclusion about why it was specified that b must be nonzero so I don't need help

[barren garden]

oh ok thank you

i am still horribly bad at spotting when i should try contradiction

[radiant sundial]

it should be used judiciously, especially in cases where a direct proof is feasible and more straightforward.

[barren garden]

anyone know if there is a direct proof that d divides a?

[still flare]

If you know that d is gcd(a,b) then it's immediate.

As for some proof that doesn't use that, I don't immediately see a way.

[barren garden]

:S

[still flare]

Actually, I worked it out on paper and it's not hard.

Would you like a hint or should I just show you the method?

In any case I'll write a hint.

[barren garden]

i'd love a hint

[still flare]

Suppose the minimum is some d = ax + by, and suppose d does not divide a, so it has some nonzero remainder which is less than d. Write out what that gives you, and rearrange :)

Fixed a typo.

[barren garden]

oh yeah i did exactly that after a hint from ryx, but that's not a direct proof, which is what i was wondering if there were :S

[still flare]

So you don't want a proof by contradiction

Yeah good luck

I forget that people use 'direct proof' in a weird way. I consider this proof to be very direct.

[barren garden]

[still flare]

If you like, you can argue this by strong induction: I am showing that no bound greater than 0 on the remainder of a modulo d exists

But this is a needless rephrasing of the problem

[barren garden]

[radiant sundial]

I think he or she can proof directly

right?

[still flare]

Be my guest

[radiant sundial]

We want to show that d divides a, which means there exists a natural number k such that a=dk. Since d = ax_1 + by_1 where x and y are integers a = (ax + by)k, so a = ax_1k + by_1k (since all a,b,x_1,y_1 are all integers) we can say a is a multiple of d, therefore d divides a

does this proof work?

[barren garden]

i think you're assuming what you want to show when writing a = (ax+by)k

which is not a proof

[radiant sundial]

I forgot to add subscripts under x and y

it should be x_1 and y_1 (where x_1 and y_1 are integers)

[radiant sundial]

reread it again

check if it is now a valid proof

[still flare]

It's not.

You still assume the conclusion.

[radiant sundial]

Ok then another way to proof

we use a=qd+r where 0<=r<d

this time I hope it actually proves

without assumptions

[barren garden]

true mathematical sentences without assumptions are typically very uninteresting

[normal heart]

I will never understand why one would persist in using direct proofs instead of contradiction

[barren garden]

i just find it interesting when both are possible

[radiant sundial]

Let a = qd + r, where q is a quotient and r is the remainder. when a is divided by d. 0=< r < d
d = ax_1 + by_1 for some integer x_1 and y_1.
r = a - qd
r = a - q(ax_1 + by_1)
r = a (1- qx_1) - b(qy_1)
r is linear combination of a and b, which means r is a multiple of d
since 0=<r<d the only possibilty is r = 0. so d divides a without leaving a remainder

Please tell me this works 😭

[barren garden]

first line should be qd not qx, otherwise looks good

[radiant sundial]

my mistake 😭

its 12 am

I am supposed to sleep...

[radiant sundial]

Ez win 😎

[patent acorn]

r is linear combination of a and b, which means r is multiple of d
...what? why?

[barren garden]

linear combination in a and b

oh

the claim is true i'm fairly certain, but should probably be elaborated on

i conclude rather from the linear combination that d <= r

but since r < d we get a contradiction

[charred roost]

I'm trying to show $p^{q-1} + q^{p-1} \equiv 1 \pmod{pq}$ for primes p and q. From Fermat's theorem I have $p^{q-1} \equiv 1 \pmod{q}$ and $q^{p-1} \equiv 1 \pmod{p}$, but I'm a bit stuck on how to combine them

[sterile pumice]

sheddow

[charred roost]

I assume I need to use Bezout's identity (px + qy = 1) somehow, since the conclusion requires distinct primes p and q

I tried to write $p^{q-1} = 1 + tq$ and $q^{p-1} = 1 + sp$, giving $p^{q-1} + q^{p-1} = 2 + tq + sp$. Is this the right approach?

[sterile pumice]

sheddow

[normal heart]

Consider chinese remainder theorem

[radiant sundial]

Do q^p-1 in mod q

[barren garden]

i’m asked to calculate 2^(2^20) (mod 2^20 - 1), but i’ve no idea how to simplify this >.< it looks fermat’s little theorem but i don’t know whether 2^20 -1 is prime or not (indeed they ask about this later)

my guess is i’m just supposed to calculate the rest and conclude (from the contrapos of fermat’s little) that the number is not prime

[fiery zenith]

i think i can see a factorisation.

[barren garden]

oh wait say no more

thanku

[white lion]

Note q^p-1 = 0 (mod q) likewise p^q-1 = 0 (mod p)

[cerulean rivet]

What is an aggregate lol

[barren garden]

ok nvm i’m still getting nowhere

god i’m so bad at number theory

i’ve only found that i can write $2^{2^{20}}$ as $2\prod_{k=0}^{19} 2^{2^k}$, which doesn’t seem to help…

[sterile pumice]

Jens

[barren garden]

i suppose it’s simplified it a little

if i can just find $2^{2^k+1}$ mod $2^{20}+1$ for each $k=0,1,\ldots,19$ i would be in a good place

[sterile pumice]

Jens

[barren garden]

@fiery zenith any hints?

[fiery zenith]

i was referring to the thing u asked is prime or not

[barren garden]

right, thanks

[whole bronze]

U_{2^k} is the group of units modulo 2^k

I'm so lost on how to prove this

(2^2+1)^(2^(k-2)) and then try to reduce modult 2^k?

[fiery zenith]

i think so

[whole bronze]

expanding by the binomial theorem only gives you one term you can eliminate

[fiery zenith]

but wheres the group theory tbh

[whole bronze]

I don't see how to do it even without group theory

[fiery zenith]

well what group theory does it expect

[whole bronze]

I have no idea

probably not anything too advanced

[fiery zenith]

well try #groups-rings-fields ig

funny how they phrased it

[whole bronze]

ok doing induction on k works, but that's not group theory lol

[fiery zenith]

#groups-rings-fields message

[whole bronze]

thanks!

[barren garden]

looking at it further… it seems they actually want us to calculate each 2^(2^k) and the product… evil

it helps at least that each factor is the square of the previous

ok i’m skipping this, lol

[whole bronze]

Maybe put this in wolfram alpha replacing 20 with k and looking at the answers for 1<=k<=20

Maybe there will be a pattern you can prove with induction

I haven't had time to actually test this though

[barren garden]

hmm

ok more helpful:

it gets locked into a cycle from k=5, phew

[whole bronze]

Ok that looks horrible

[barren garden]

nono we good

thanku very much

[barren garden]

i had tried to calculate by hand the value for k=4 but gave up haha, calculating k=5 (which apparently gives a value over 2^20) i wouldn't stand a chance... guess i'll just list the first 9 values in my solution and say i found them using a computer

[whole bronze]

Actually k=5 isn't too bad

2^32 = 2^20 × 2^12 = (2^20-1) × 2^12 + 2^12

[barren garden]

ooh

[whole bronze]

Then reduce mod 2^20-1

[barren garden]

something similar should work for k > 5 as well

[whole bronze]

And you can prove it repeats since it's just repeated squaring

[wooden glen]

Working modulo 2^k-1 is the same as declaring that 2^k=1, so we'll also have 2^n = 2^(n mod k).

[barren garden]

[whole bronze]

Ooh that's nice

[barren garden]

this problem is suddenly very easy mwahaha

thanku thanku tropos

[wooden glen]

For whether 2^20-1 is prime, note that it is the same as (2^10)^2 - 1^2.

[barren garden]

...which is equal to (2^10 + 1)(2^10 - 1), lovely

[wooden glen]

And it is fairly easy to see in general that 2^k-1 cannot be prime if k is composite.

[barren garden]

i have been planning (since last christmas) that my next vacation (which is for christmas) i will spend in entirety trying to get some grasp on elementary number theory

i have tried to get into it a number of a couple years now, but i always struggle so right from the get-go, it's weird

i will bring both silvermann's friendly introduction and andrews number theory to venice

actually i might have to rethink that combination into a more complementary pair hmm, but certainly silverman i will bring

[barren garden]

oop i just realized i've misread and the question asks for mod 2^20 + 1 not 2^20 - 1... does a similar thing work somehow?

something like

[ 2^k \equiv (-1)^{\lceil k/n \rceil} 2^{k\bmod n}\ ?]

[sterile pumice]

Jens

[barren garden]

perhaps

[wooden glen]

In that case we've declared that 2^20 = -1, so 2^40 = 1, so 2^n = 2^(n mod 40) instead.

[wooden glen]

That works too, I think.

[barren garden]

negative numbers are a bit of a pain in congruence classes though, i think i prefer 2^n = 2^(n mod 40)

[barren garden]

or hmm i only actually need $\lceil k/n \rceil {\pmod 2}$ which might simplify but i don't see any straightforward way to do so

[sterile pumice]

Jens

[sacred junco]

Where would I even begin with this? My original thought was to get the square root on both sides, but that would just be 1 either way, so X3 should be 1 right?

[patent acorn]

well you're right that 1 is one solution, but there is another number that squares to 1

[barren garden]

finally got a somewhat satisfactory answer, thanku very much for the hints @whole bronze @wooden glen

[sacred junco]

I know it can't be -1, it only allows answers >= 0

Maybe I'm missing something lol

[eternal shoal]

What is equivalent to -1 mod 13, between 0 and 12?

[patent acorn]

who said that -1 isn't >= 0?

[eternal shoal]

nevermind the fact that we shouldn't be ordering stuff modulo n

[sacred junco]

Hm, still at a loss here. I know 1 is absolutely one of the answers, but isn't -1 objectively < 0?

1^2 is congruent to 1 (mod 13), and I know that -1 would be as well

[eternal shoal]

-1 should have some equivalent number (mod 13) between 0 and 12. This might help.

At least, last time I checked it did

[sacred junco]

Ah, just got it

It'd be 12 right?

[patent acorn]

isn't 12 < 0 though?

(serious answer: yes it is 12, 12 = -1 mod 13)

[wooden glen]

Uh, if n = 2^20 + 1, then 2^(n-1) = 2^(2^20), not 2^(2^20 - 1).
So you don't need to write your target as that indexed product of 2^(2^k)s.

[sacred junco]

I do think I need a bit of an explanation though. 1 % 13 is 1, but 12 % 13 is 12. How could 12 be equivalent to -1 (mod 13)?

Unless I'm overthinking it on the first half with the ^2

[patent acorn]

13 = 0
subtract 1 from both sides
12 = -1

[sacred junco]

oh lol

[patent acorn]

alternatively: what's -1 % 13?

[sacred junco]

Ahh I see

[barren garden]

oops yes thanks i alraedy cleared up parts of that mistake elsewhere but forgot to fix it there

and as you can tell by my spelling i am very sleepy

[wooden glen]

The definition of "equivalent mod 13" means that 12 - (-1) should be a multiple of 13 -- and since it is indeed 13 itself ...

[sacred junco]

Gotcha

Ty for the help everyone!

[white lion]

Fun excercises for you prove that if a^2 = 1 (mod p) then a = -/+ 1 (mod p)

[hot brook]

too pluhs too ehs foh, meyenus wun das tree quick mafs

[barren garden]

did i mess up the contrapos or something here, this feels too simple

[barren garden]

i suppose i should give special attention to the case n=2

[charred roost]

Nice proof 👍 I much prefer yours to the one in my textbook:

[west glade]

your proof doesn't work for n=p^2, p prime

@barren garden

[barren garden]

oh? i don’t see how

[west glade]

well the only way to choose a,b would be a=b=p. but then p only appears once in the factorial

[barren garden]

ooh right

i implicity assume a and b are distinct, which is not necessarily the case

hmm

and i don’t see an easy fix for the case a = b

.<

[west glade]

try it for n=9 explicitly

well and n=4 is of course also special

[barren garden]

3 has no multiplicative inverse mod 9 ?

[west glade]

write out 8!. why is it a multiple of 9

[barren garden]

oh right because of 6

[west glade]

yes

[fiery zenith]

3.333333333

[tired pagoda]

hello all I may have an important discovery to share relevant to elementary number theory and possibly even the riemann hypothesis. its a relation between the intersection of perpendicular sinusoids, pi and, prime numbers.

while there have been relations discovered between sinusoids and prime numbers such as using them to calculate all possible primes(given enough time) this exact relation has yet to be discovered. additionally as far as I can tell this relation is also capable of confirming if two numbers are the factor of a prime.

[sacred junco]

if two numbers are the factor of a prime
Step 1. Check that one of them is 1 and the other is a prime number

[normal heart]

[tired pagoda]

https://www.desmos.com/calculator/wfggb5uhio

as you can see from the preview there is an intersection of the sinusoids wherein the intersection is two points of slope zero. the only time at which this occurs is when d is a prime.

[sacred junco]

Could you highlight these intersections?

[tired pagoda]

yes one second

[open mist]

you mean this ?

[tired pagoda]

yep

https://www.desmos.com/calculator/lb3diihu5y

heres the updated page with highlighting

[buoyant mason]

i can think of a simpler way to write this

[open mist]

@tired pagoda this image is for d=15
Not a prime

[tired pagoda]

frick your right im stupid. however it interesting that primes as far as it seems will always result in such an intersection although it does seem other numbers will work.

[open mist]

as far as my testing goes, it detects odd numbers

[tired pagoda]

plug in any prime number and look at the highlighted point and that intersection will occur. I will have to do a bit of exploring to determine what causes other numbers to such as 15 to result in such an intersection. thinking about it now im guessing the reason is that d= (15*pi)/2 will result in a value for t that also can be achieve through a prime.

[sacred junco]

@tired pagoda Seriously, it's just an odd number detector

[tired pagoda]

then plug in d=2 and j=4. why do you need to change j to =4 well because (2*pi)/2 is just pi.

[sacred junco]

sin(x)*dpi/j=dpi/j is the equation that gives you the intersections here

Sorry no, small detail

[open mist]

j=4 now let's you detect all numbers that are 2 mod 4 it seems

[sacred junco]

Actually nevermind this is correct

wait

frick

asdjlaisdj

Okay okay my brain just did a reboot

[open mist]

Idk I didn't look at the math yet

[sacred junco]

It's actually sin(x)*dpi/j=x I don't know why I had such a stroke

...I think I'm missing some absolute values

I don't think the stroke went away give me 2 seconds

[tired pagoda]

k

[open mist]

claim:
It detects all values that are congruent to j/2 mod j (works for odd j too)

still didn't look at the math, I trust you with that

[sacred junco]

Incorrect, there are no integer intersections for j=3

[sacred junco]

don't

[open mist]

how surprising, since j/2 isn't an integer in that case

[sacred junco]

hmm

[open mist]

still aligns with my claim

[sacred junco]

me no see where you're going

[open mist]

me have made claim

[sacred junco]

1.5 sound like integer to me

[open mist]

you have not disproved claim

[sacred junco]

I feel personally attacked

I'm calling 911

[normal heart]

1.5=0 mod 3

[sacred junco]

oh wait I'm in France

[open mist]

wrong country

it's 17

or if you're hurt, 15

18 if it burns

[sacred junco]

The 911 equivalent is 112

[open mist]

shhh

[sacred junco]

or at least that's what we're told

[open mist]

it's the joker card when you don't know who to call

that's why it's EU

notice it's the sum of the descriptions of 15, 17 and 18

[sacred junco]

You're missing a pi/j factor but yeah

[tired pagoda]

I have no clue what mod means im only 16 and am just beginning to understand calculus. I just posted in elementary number theory bc it related to the primes. it does indeed seem I just made an odd number detector. I think I might be able to modify the equation for t to detect primes and then see if the same pattern emerges. if it does I might be on to something if not well I just got excited thinking I found a pattern to prime numbers.

wait mod is short for modular arithmetic never used it but I have a surface idea of what it is.

[open mist]

I'm looking at the value of d

[sacred junco]

Okay yeah I am missing an absolute value

|sin((kj+j/2)pi/j)|*dpi/j=|sin((k+1/2)pi)|*dpi/j=dpi/j

This must be equal to j(k+1/2) it to be an intersection

[open mist]

it's not
yes
you won't
you're not
stay curious
But don't just throw RH in there for good measure when you didn't even notice d=9 failed, and you made an odd number detector

[sacred junco]

oops

[open mist]

not to brag, but I've yet to have said something wrong here

[sacred junco]

ok

[open mist]

randomly says my claim is wrong on the 4th generalization, in a way that would make it fail on the 1st claim

[sacred junco]

This must be equal to (kj+j/2)pi/j=(k+1/2)pi*

[open mist]

does look like j/2 mod j to me

[tired pagoda]

wait wait no d=9 when j=2 for t=(d*pi)/2 will result in an intersection of points slope zero. here lemme screenshot it real quick.

[open mist]

yes

but 9 is not prime

hence you should have known it's not a prime detector

[sacred junco]

That's because I picked a j/2 mod j value from the beginning

[open mist]

find a detection for any other value of d I dare you

[sacred junco]

no

[tired pagoda]

right nvm

imma try to work on t only accepting prime values and see if I get anywhere.

[open mist]

that one was the 3rd line

[open mist]

https://www.youtube.com/watch?v=j5s0h42GfvM&ab_channel=EricRowland
That's the best known formula for generating prime numbers using trig afaik

[sacred junco]

why did I write d even though I set d=kj+j/2 asjdikasldjs

Anyways, j/2 mod j does work

That's not just for j being an integer

It's for any j

[open mist]

already said that

[tired pagoda]

I dont really need to generate primes I need to check if a number is prime and if not get t=0 or perhaps an even number ensuring that no intersection at points of zero slope occurs.

[sacred junco]

That's not gonna happen by just doing random stuff with sine functions

[open mist]

indeed

[sacred junco]

By the way, as far as I remember, inside of this formula is something that checks whether a number is prime

[open mist]

you don't just bring arithmetic into smt by accident

[open mist]

it's engineered all the way down

[sacred junco]

You know, technically they're not wrong

[tired pagoda]

bet/j im wrong but imma try anyway. its not to infrequent that the solutions to long unsolved problems are relatively simple.

[sacred junco]

It does detect prime numbers

[tired pagoda]

im probably just wasting my time tbh

[patent acorn]

...is it?
when has that ever happened before

i can think of a lot of cases when it didn't but not any when it did

[sacred junco]

Yeah but typically those solutions are found through ingenious insight, not random play

[sacred junco]

Wasn't Fermat's last theorem proven using p-adic numbers? I never saw the whole proof but the idea seemed relatively simple

[tired pagoda]

true true im basically the math equivalent to a script kiddy.

[sacred junco]

A script kiddy doesn't play around with lines of code at random when they have a specific goal in mind

[tired pagoda]

true as well

you know perhaps there isnt a pattern to the primes and if there isnt perhaps a more interesting avenue of exploration is why there isnt a pattern to the primes if there isnt. maybe if we look for reasons why there arent we will find a reason why there are and from there a pattern or maybe we wont maybe we will just find that there isnt and why not. where to start in that regard however I have not the foggiest of intuitions.

[patent acorn]

well there are a lot of patterns in the prime numbers

...most noticeably there's the fact that prime numbers never seem to have any divisors other than 1 and themselves

which also implies they're always equal to either 1 or 5 modulo 6, if you exclude 2 and 3

[open mist]

there are many theorems on the distribution of primes
The ones that are deterministic say there's no pattern
The ones that say they're randomly distributed but end up in certain patterns are beautiful

an example of the first one would be that besides not possibly being polynomial, they're also not given by any recursive linear sequence

an example of the latter would be Dirichlet's theorem

and the equirepartition part of it

[open mist]

which would state that there's about as many primes that are 1 mod 6 and 5 mod 6, for example

but as soon as we try to have something constructive, it gets real hard if not impossible

[tired pagoda]

yeh desmos doesn't really like Willans' Formula. can someone link some graphing software that supports more than implicit equations of x and y?

[open mist]

use an actual calculator
And a powerful one, not your school calculator

[tired pagoda]

so not a ti84+

[open mist]

it takes just about 5000 terms, and therefore about maybe 1 million elementary operations, to find the 10th prime

that's why it's a joke: it's absolutely unusable

[open mist]

clearly, by looking at the formula again, it revolves around detecting when Wilson's theorem applies
As simple as that

[open mist]

nvm there's a j!
Without optimizing it's much worse than that

[open mist]

this formula is basically just running an awful (but purely computational) primality test and doing some shenanigans to turn it into a counting/generating function

[tired pagoda]

hmm maybe I can just use the detection section instead of trying to use it to generate shit. on a separate topic if you take my original set of functions and add z after y and x after the = in a 3d graphing software you end up with some very interesting patterns.

try hiding all but one of the functions in this case it doesnt really matter if your chosen value is odd or even.

[open mist]

just because something looks cool doesn't mean it has to do with primes

[tired pagoda]

yeah I know Im just saying it causes some interesting fractal wave patterns. I wasnt relating it to the primes because it looked cool in the slightest im smarter than that.

[open mist]

the detection section relies on :
Wilson's theorem:
if p is prime, then (p-1)! = -1 mod p (and in fact, this product is 0 mod p if p isn't prime)
Hence floor(cos²(((p-1)!+1)/p)) is 1 iff p is prime, and 0 otherwise
Or just compute the cos and test whether it's equal to 1 or -1 (though you may deal with floating point errors rather quickly, making it rather unreliable in practice, even for very small primes)

[tired pagoda]

thanks I will use that if possible. heres the aforementioned patterns I was talking about(zoom out a bit)https://www.desmos.com/3d/6feb94848a

also excuse the title that was its name a while ago and I have since rejected that theory

https://www.desmos.com/3d/9eae080219

this is already zoomed out your actually going to want to zoom in on this one.

anyway this is kinda off topic from the channel at this point so imma shut up and keep on a tinkering.

[sacred junco]

How many 5 digit numbers have the propriety that dont contain 2 consecutive prime digits?

[whole bronze]

I tried considering the fact that x^d = 1 iff ord(x)|d and by Lagrange's polynomial theorem stating that nontrivial polynomials of degree d have at most d incongruent roots, we conclude that the numbers of elements of order dividing d is at most d.

Weakening this, we get that the number of elements of order exactly d is still at most d, but we want phi(d) as a bound instead.

I don't see how to get phi(d) as a bound

do we need to use this?

I don't see how I would....

[open mist]

(Z/pZ)* is cyclic, so it's isomorphic to U(p-1)
from which, we know that an element of order d is a d-th root of unity and no lower than that,
i.e. it's a primitive d-th root of unity. We know there's phi(d) of them since Ud is isomorphic to Z/dZ (the generators of which are well known)

[open mist]

that tells you these upper bounds are actually maximal, since that's the only way for every element to have an order

[whole bronze]

The screenshot was a step in proving that Z/pZ is cyclic, so that wouldn't be allowed to be used

[open mist]

(looking at these polynomials, this is the same reason that the cyclotomic polynomials multiply to X^d-1 and the d-th one is of degree phi(d), you just need to rephrase it in terms of groups (since you probably can't tell cyclotomic polynomials for granted))

Every element whose dth power is 1 is a root of X^d - 1, and we know there are at most d of those.
Consider then, an element of order d. That means it generates a group of elements whose d-th power is always 1, and this group has exactly d elements. This group, by definition, is cyclic, and clearly, the set of roots of X^d - 1.
So the roots of X^d - 1 make a cyclic group of order d. Taking one of those generators to be mapped to 1 gives us an isomorphism with Z/dZ, for which we know there are phi(d) generators.

Note: this means if there's an element of order d, there's exactly phi(d) of them. One can prove there must be one, like before, using sum (phi(d)) = n, to argue that if one d had no element of that order, there wouldn't be enough elements to make a group of n elements

[barren garden]

whaaat, does this hold for any natural n?

[whole bronze]

Yes, list the fractions i/n for i in {1,2,...,n}. There are n of them. Reduce to lowest terms and count and get the lhs.

[barren garden]

amazing

[fiery zenith]

0

[wooden glen]

1+1+2+2+4+2+6+4+6+... = 0

[restive ruin]

help any1
idk if this is under no. theory or algebra

[open mist]

algebra, because the proof uses no number theory

You want to prove one of the discriminants is negative. That's guaranteed if the sum of the discriminants is negative.
Find that sum by using the fact the 2 equations can be rewritten to give you the sum of the ak and the sum of the ak², and therefore the sum of the discriminants

[restive ruin]

ohh
thanks

[weary palm]

do yall recommend any books to study NT?

[still flare]

#book-recommendations

[pine cave]

hello

there is a conjecture i have (without too much evidence, but it doesn't really matter because i don't need it to be true or anything) about the final digits of arbitrarily high hyperoperations in different bases

and when trying to investigate it, i quickly ran into the limits of the techniques i know how to use (which are the very trivial modular arithmetic ones) and i know of the existence of some slightly more advanced techniques involving totients that i don't know how to use and i was hoping someone could teach me some of those techniques (and perhaps provide further guidance on the problem, but first things first)

so first of all, the conjecture and its shaky basis: i learned, or maybe independently discovered, don't remember which, about the aforementioned very basic techniques for calculating the final digits of quite high powers and this inspired me to do some investigation of them

i discovered something that took me by surprise; it appeared to me that (in base 10), tetrations greater than 2 are capable of ending with every digit but 8
i did not, in fact, actually prove this, merely convinced myself it was true by examination and some limited computation

and by the same process of examination and limited computation in other bases, gave me a suspicion that prime bases, and perhaps only prime bases, exhaust the digit possibilities

this was quite a while ago, and since then i have really wanted to properly prove the facts involved to be able to state anything definitive about the matter at all

but when sitting down to actually do it it became obvious to me that i do not know enough to prove it; i got stuck on basically step two of the investigation, which is to prove that tetrations by >2 of 3 always end in 7

[wooden glen]

Suppose you want to know, say, the last 5 decimal digits of a power tower 3^3^3^3^3^...
Then thanks to Euler's theorem, 3^3^3^... == 3^(3^3^... mod totient(10^5)) (mod 10^5)
But that again is the same as 3^(3^(3^3^... mod totient(totient(10^5))) mod totient(10^5)) and so forth.
And when you iterate the totient function starting from 10^5, you'll fairly quickly reach 1, and from that point onwards the rest of the power tower cannot matter because you're taking it modulo 1.
In particular it doesn't matter how tall the tower is, as long as it's not very short -- so all of the higher hyperoperations except the first few will give five last digits that depend only on the base value.

But we don't even need to be that sophisticated to exclude 8:
The last digit of any power of x depends only on the last digit of x, and on the exponent.
In order for any power of x to end with an 8, x needs to end with an even digit (otherwise all its powers are odd and don't end with 8).
Powers of 2 end with 8 iff the exponent is 3 modulo 4 -- but that's not the case for any exponent that's itself a power of 2.
Powers of 4 end alternately with 4 and 6.
Powers of 6 always end with 6.
Powers of 8 end with 8 iff the exponent is 1 modulo 4 -- but again, that cannot be the case for exponents that are themselves powers of 8.
So it's impossible for any number of the form x^(x^y)) to end with an 8, no matter what y is.

[pine cave]

yeah that's basically what i came across but i didn't write down all the steps of my argument so i wasn't entirely sure it was valid haha

[wooden glen]

Concretely: Since totient(10)=4, the last digit of 3^(3^(3^z))) only depends on 3^(3^z) mod 4.
In turn, totient(4) is 2, so 3^(3^z)) mod 4 only depends on 3^z mod 2. But 3^z is clearly always odd, so 3^(3^z)) mod 4 is always 3.
And therefore 3^(3^(3^z))) is always 7 modulo 10.

[pine cave]

ooh, right, okay

yeah i was trying to figure out how to utilize that totient property but it wasn't entirely clear to me how to repeatedly apply it like that

[wooden glen]

It is true that prime bases do give us all the possible last digits for high tetrations. Namely for base p, if we want tetrations ending with d, use the Chinese remainder theorem to choose x such that x==d (mod p) and x==1 (mod p-1). Then x^(x^n)) == d (mod p) for all n.
But we can do this for every base that is coprime to its totient, and such a base doesn't need to be prime. For example, it also works for base 15.

[pine cave]

oooh

[white lion]

Elementary introduction to Number Theory by Long (3rd edition)

[white lion]

I’m trying to understand why when we have a given linear congruence say ax = b (mod m), with d = (a,b), finding x in mod m/d gives us our solution.

My understanding of it is, that if there indeed does exist a solution, then we know that all the other solutions must differ from it by a multiple of m/d. So we suppose x is a solution and if we solve for it in mod m/d. Then we found another solution, and from this numerical solution we can use it to find the rest, is this understanding correct?

[vapid falcon]

can someone generate the sequence {2,16,54,128,250,432,686}

[torn escarp]

why

[dusty dragon]

let f : {1, ..., 7} -> Z such that f(1) = 2, f(2) = 16, f(3) = 54, f(4) = 128, f(5) = 250, f(6) = 432, f(7) = 686

[vapid falcon]

i guess that's correct

try {2,16,54,128,250,432,686...}

[dusty dragon]

it'll be much clearer when you ||divide by 2|| :-)

[vapid falcon]

thanks

[weary palm]

is there a way to take the dirichlet character of a fourier series?

[torn escarp]

i dont see any police around

[wheat tinsel]

,w interpolate (1,2), (2,16), (3,54), (4,128), (5,250), (6,432), (7,686)

[sterile pumice]

Results provided by WolframAlpha

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

Requested by Croqueta#3385

[wheat tinsel]

xD

[wraith topaz]

this might be a silly counting thing which I'm struggling with, but I had this question which asks how many positive divisors 2^r 3^s 5^t has, and I wasn't sure how to prove it should be (r+1)(s+1)(t+1)

ig it has to at least be r + s + t bc that's the number of prime factors but I wasn't sure how to incorporate multiplying out prime factors, or if there's a better way of enumerating the positive divisors which doesn't involve counting at all (I've seen some stuff about multiplicative functions from cursory glances online but we've only really discussed divisibility in class so I've been discounting it if there's a different way)

[loud maple]

The idea is to think about how the prime factorisation of an arbitrary factor of this number looks

[wraith topaz]

I mean an arbitrary factor would have the prime factorization 2^a 3^b 5^c, ig those can be 0 <= a <= r, etc, can we just say an arbitrary factor has (r+1) possible options for 2, (s+1) for 3, (t+1) for 5

[whole bronze]

Testing out Legrange's polynomial interpolation where the points being interpolated are all points on the integer lattice, I notice the polynomial always outputs integer values even for inputs that were not in the set of points being interpolated. Does anyone know a reason for this?

actually this is not true at all

we at least need the restriction that the x-coordinates of two of the points being used for the interpolation be adjacent

or all of the inputs to be adjacent

for example, if the points are (0,5), (1, 3), (2,6), (3, 8) and P is the interpolating polynomial, then P(Z)\subseteq Z

[wooden glen]

You definitely need all the sample points to be consecutive integers; just one pair of neighbors is not enough. E.g. consider f(0)=0, f(1)=0, f(3)=1.

In the consecutive case it's enough to show that the property is true when one of the sample function values is 1 and all the rest are 0. (All other interpolations will be integer combinations of those).
Without loss of generality, suppose we want f(0)=0, f(1)=0, ..., f(a-1)=0, f(a)=1, f(a+1)=0, ..., f(a+k)=0.
The interpolating polynomial is then x(x-1)···(x-(a-1))(a+1-x)···(a+k-x)/a!k! -- but that is the product of the interpolating polynomials for the points 0 through a and a through a+k, respectively -- so it's actually enough to consider the case where the 1 is at the end of the sequence of sample points.
Thus let's assume k=0. The interpolating polynomial is now simply x!/(x-a)!a!, that is, the binomial coefficient x-choose-a, which is an integer when x is.
At least, that is, when x is positive. But it's easy to see that we also get f(-1)=±1, so up to a sign the interpolating polynomial behaves the same way to the left of the sample points.

[foggy linden]

State true or false.
Let m and k be positive integers. If r^k is a primitive root modulo a positive integer m, then r is also a primitive root modulo m.

I am inclined to think that it should be false but, apparently, it's true.
I have been unable to find a counter example.
I'm using this - If order of r is p, then order of r^u is p/(u,p). According to that, r and r^k will both be primitive roots only if k and Phi(m) are relatively prime. Question whereas seems more lax about k.
Of course, it's not a valid argument because i'm assuming that a non-primitive number is generating a primitive root which, probably, can't happen but i am not able to see the reasoning behind that.
Any help/hint/insight is appreciated. Thank you.

[west glade]

well in particular the order of r^k cannot be more than the order of r. so if r^k is primitive then the order of r must be at least as high, so r is primitive aswell

[foggy linden]

Okay, yes. That simply follows from that theorem that i mentioned. GCD can't be less than 1 for integers.
Same reason for why a non-primitive number can't generate a primitive root.

Btw, is there some more intuitive reasoning for this? Asking, in case, you have some better explanation.

[west glade]

well every integer that r^k can generate, r can generate obviously aswell

cause (r^k)^n = r^(kn)

[foggy linden]

Mod wouldn't really make a difference.

[foggy linden]

Okay. I get it but when i think about it other way around. It's like- r^k would generate r^kn for power of n, but r would generate r^kn for power of kn. kn can be bigger than Phi(m) as k is kinda arbitrary. It just has to be smaller than Phi(m). Since r is primitive, r must be generating r^kn for a power less than or equal to Phi(m) but that's not exactly evident to me.

[west glade]

the power can be bigger than phi(m), that doesnt matter

the exponent is basically mod phi(m)

[foggy linden]

Okay. Yes. I thought of that. It just felt awry for some reason. I got it though.
Thank you.

[foggy linden]

I have one more question which i think can be answered similarly. If possible, please take a look at my justification.
Question: A number can't be both a quadratic residue modulo an odd prime p, and a primitive root modulo p.

So, let's say that for some number r, r^2 is our QR. Now, assuming that r has an order t, then r^2 has order less than t. So, r^2 can't have order equal to Phi(p).
If p was 2, then it would have worked but we have p, an odd prime.

Once again, am i missing some very simple approach?

Sorry for the ping. I wouldn't do it next time if it's bothersome.

[west glade]

well where are you using that p is odd

why does your proof fail for p=2

[foggy linden]

Question said that p is odd.

Proof fails for p =2 because Phi(2) = 1.

GCD(1,2) = 1, so O(r^2) = O(r)/(1,2) = O(r)

Basically, for p=2, 1 is the only primitive root and any power of 1 is just 1.

[west glade]

what I wanted to hear is that gcd(2,p-1)=2 because p is odd

and so the order of r^2 is t/2

[foggy linden]

Yes.

So, this is fine?

[west glade]

yes thats how the proof goes

[foggy linden]

Thank you very much.

[sharp knot]

heya, taking modern algebra at my university and wanted my logic checked on something real quick. it isn't rigorous, but i want to know if the intuition holds up at least

the number of self inverses in Z/Zn (ie, |{a | a^2 = 1 mod n}|) depends on the factors of n
if n is prime, then the congruence classes of 1 and -1 are self inverses, and that's it
if n has prime factors p and q, then the elements of Z/Zn can be classified by their modulo p and their modulo q
a number that is 1 or -1 in both p and q is also a self inverse
this gives 4 possibilities
generalizing, for any modular group with k distinct prime factors, the number of self inverses will thus be 2^k

is this true? can anyone readily present a counterexample with either more or fewer self inverses?

[plucky jacinth]

n=2 has only one, not two

[meager reef]

Seperate the 2 case because it usually is known to not behave similarly as odd primes.

Otherwise, it's fine. Chinese remainder theorem should help.

[sterile pumice]

Riku

[meager reef]

See if this works for your generalization

Oh shit I forgot the Z lol, consider it the principal ideal generated by that prime power

But yeah

if something can be considered mod p^alpha, By something similar to Hensel's Lemma, I think you have a relation to that residue in mod p

Btw if any of this is wrong please point out, I'm still learning these

[sharp knot]

Thanks for the help gang. Even if I should have learned it in class, I still managed to learn it on my own, so that feels good 😛

[white lion]

im trying to prove that $a^{2^n} \equiv 1$ (mod 2^{n+2})$, where a is an odd integer. But, I think it's wrong. Suppose its true, then $a^{2^n} = (2k + 1)^{2^n}$ for $k = 0,1,2 . . .$ then we can use the binomial theorem, if it is true then all the terms except the last one should be a multiple of $2^{n+2}$ but for example this particular term in our expansion, "$2^n$ choose 1" $\cdot 2k \cdot 1 = 2^n \cdot 2k = 2^{n+1} \cdot k $, when k is one the term is not a mutliple of $2^{n+2}$

so it doesn't hold for all odd integers as I wanted

[sterile pumice]

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

[serene sun]

Okay let me try here first

Identify the roots of
\begin{align*}
& (n_1 + n_3 + n_5) u \
& - (n_1 n_2 n_3 + n_1 n_2 n_5 + n_1 n_4 n_5 + n_3 n_4 n_5) u^3 \
& + n_1 n_2 n_3 n_4 n_5 u^5 = 0,
\end{align*}
given that $n_i \in \bZ$.

[sterile pumice]

Absta

[rain mirage]

what is this question asking off me

like i get its 2^1 *3^1 * 7^2

that makes up 294

but

am i meant to select 2 3 and 49

??

i did that for the next example but it was still wrong so

[open mist]

7 is a prime power and a factor of 294

[loud maple]

It is asking you to select prime powers that are a factor of 294

[glad ledge]

Can anyone help me with part b please 🙂

[white lion]

Use the fact that if a is congruent to b modulo n then the gcd(a,n) = gcd(b,n)

[stuck coral]

hey this is a number theory problem from the amatyc competition. any shortcuts for solving it? i havent had much luck testing values

[carmine tide]

reposted and answered in #competition-math ^

[silver oak]

you can exclude 2,3,5

if d is 5, then a^5 must also be divisible by 5, because 2010 is
and then each term is divisible by 25, but 2010 isn't
same for 2 and 3

doesn't solve it but still true

[west glade]

really not like there are many values of a to test

[glad ledge]

Thank you for your reply!! However I don't fully understand what the question is asking of me :/

[white lion]

Recall what the definition of the Euler phi function valued at n is - it’s the number of integers that are coprime to n not exceeding n

It’s asking you to show the the residue system of S modulo n has precisely phi(n) integers that are coprime to n.

[glad ledge]

Oh okay, thank you!! I couldn't understand how I was supposed to prove a definition lol. And you're saying I can somehow do that using highest common factors?

[white lion]

Yes, that’s what you need to show that they have the same amount of integers that have the highest common factor = 1 (I.e same amount of integers that are coprime to n)

[glad ledge]

May I ask a HUGE favour. When you're free can you baby step me through it as you're the first person I've found who understands and I'm so lost with it all :/

[white lion]

Sure I’ll be free in 2 hours or so.

We’ve all been there

[glad ledge]

Thank you so much, I really really appreciate this. I can't thank you enough

[white lion]

So what’s your issue?

[glad ledge]

How can I show that there are phi(n) integers that are coprime to n when that is the definition of it? If that makes sense. I'm so confused on how to even approach it sorry

[white lion]

the definition of phi(n) is all the integers that are coprime to n not exceeding n

S is a residue system, which means it has n integer elements that are all mutually incongruent.

[glad ledge]

Ah so I have to show that this is equal to the number of elements of S that are coprime to n? Somehow

[white lion]

yup exactly

and you can use the fact that if a and b are congurent mod n then (a,n) = (b,n)

[glad ledge]

Okay I get the question now thank you, but I don't get what a and b are in this scenario. I'm really sorry

[white lion]

a and b are just arbitrary integers

[glad ledge]

In S?

[white lion]

nope just abritrary integers, it's a fact that for any two given integers say a and b if a = b (mod n) then (a,n) = (b,n)

[glad ledge]

But what values am I comparing the hcf of?

[white lion]

the residue system and the least residue system in your case. it says it in the hint

[glad ledge]

You've lost me again. I don't understand the hint tbh. I get I'm trying to show they're the same. I just don't get how, like my head just doesn't get it atm

I dont want my slowness to take up any more of your time though. I'm heading home now and I'll try get my head around what you have said. Thank you for helping me understand what the question asks of me :))

[white lion]

Do you know the the least residue modulo n is?

[glad ledge]

I'm assuming it's the one in this lemma we were given?

[white lion]

Yes

[glad ledge]

Okie thanks

[white lion]

Informally it’s the set of all remainder or remainder representatives

[glad ledge]

Ohh okay, that makes sense. What is the first thing I have to do in solving this thing? Is there like a step by step solution (Please say yes lol)

[white lion]

I’m not sure what you mean

But here’s an argument you can use, you can fill in the details. We are given the fact that $s_i$ which is a member of the complete residue system S must be congruent to an element of of the least residue system modulo n {0, 1, . . . , n-1} (this follows from the definition, but also observe how the complete residue system and the least residue system must have the same number of elements)

Since $S_i \equiv i$ (mod n) it follows that $(s_i, n) = (i, n)$. for each i. We know that there is phi(n) i’s that are coprime with n.

[sterile pumice]

jayz

[glad ledge]

Ohhhh thank you so so so so much! I think I understand it now :)) You've been such a great help, truly thank you

[errant otter]

Uhhhh somethings confusing me
a/b mod p = a mod p * b^-1 mod p where b^-1 is the modular inverse (assuming it exists)?
But 70/8 mod 7 = 1.75
And (70 mod 7) * (1 mod 7) = 0
Am I misunderstanding modular inverses here?

[eternal shoal]

It doesn't make sense to take decimals.

[errant otter]

Ah

Only works when the division returns integers

That was silly of me

Ahem, alr that aside I was wondering if there were any efficient way to compute the sum $\sum^p_{i=1} i^k \mod p$, where $p$ is prime. (The numbers can get pretty huge, I'm meant to write an algorithm that can solve this in time). I was considering faulhaber's formula + fermat little theorem, but idk if there are other NT results which would help here. (And computing faulhaber may be an issue too)

[sterile pumice]

Kiameimon | Welt Rene

[eternal shoal]

Indeed.

[errant otter]

Sledgehammer

[errant otter]

maybe faulhaber has some nice simplifications with modulo p

[eternal shoal]

Uhh do you get any nice cancellations here?

[errant otter]

Idk, trying to work it out, but ofc bernoulli numbers are..... not very nice to play with

[eternal shoal]

Like for p =/= 2, this should sum to 0 by pairing i and p-i

[errant otter]

Wait a sec

[eternal shoal]

Yeah... that might not be the nicest approach

[eternal shoal]

I meant for k = 1

But I am thinking this idea should(?) extend to higher powers of k too by binomial expanding

[errant otter]

mfw floating points

[eternal shoal]

Like when you expand (p-i)^k, you get p^k + (kC1) * p^{k-1} * (-i) + ... + (-i)^k. But the p factors out of the first few terms, and this is equivalent to (-i)^k mod p.

which uhh does not cancel out when k is even does it

but for k odd this should work.

[errant otter]

I mean if it doesn't ita fine

Just like

Multiply (the even exponent -1)

And then multiply 1 more time to compensate

[eternal shoal]

(and this is trivial for p = 2. So let's assume p is odd)

[errant otter]

Ngm

[eternal shoal]

whaaa

[errant otter]

Like

Since it doesn't work for even exponents

[eternal shoal]

i dunno that that works the way you think.

[errant otter]

I can just do a^x (where x is the even number) = a^(x-1) * a

And a^(x-1) is odd so the formula applies(?)

[eternal shoal]

my point is that the entire sum cancels to 0 when k is odd. Because 1 + 2^k + ... + (p-2)^k + (p-1)^k = (1 + (p-1)^k) + (2^k + (p-2)^k) + .... ~equiv~ (1 + (-1)^k) + (2 + (-2)^k) + ... = 0 when k is odd.
But this same idea won't work when k is even I think(?) since the "applying for k-1 them * a" changes as a changes

[errant otter]

Ah

Wait why does it become ... (2 + (p-2)^k)

[eternal shoal]

Like taking p = 3 and k = 2, we get 1^2 + 2^2 = 5, which is not equiv to 0 mod 3

[eternal shoal]

I rearraged the terms, which we can do since it's a finite sum. So i paired the 1 and (p-1). Then the 2 and (p-2). Then ....

[errant otter]

Yeah but isn't it 2^k and (p-2)^k

[eternal shoal]

ahem

yes

my bad

[errant otter]

it's alr

[eternal shoal]

But uhh for k even? After doing some thorough case checking (read: up to p = 7), I think we actually can simplify it still

(p is an odd prime) For even k < p-1, it still(?) gives 0. and for k = p-1, it reduced to p-1 mod p it seems

[errant otter]

Mmm, no surprise, that's flt in your last observation

But < p-1 is

[errant otter]

Wait

I'm clowning

🤡

cough cough anyways

Wait it is, sum from 1 to p of a^(p-1) mod p
Is sum of (a^(p-1) mod p)
Which is sum of (1 mod p), aside from the pth term, that is 0 cuz modulo
So it's sum of p-1 terms

[eternal shoal]

oh duh

[errant otter]

But yeah using this fact

We just need to consider 1 < k < p-1

Cuz anything more we can just apply flt and reduce it to that

[eternal shoal]

forgor about fermy's wittle theowem

[eternal shoal]

that one i don't know off the top of my head how to get it.

[errant otter]

[errant otter]

If k = p-1 answer is p-1
If k = p, answer is 0, because sum of 1 to p (i^p mod p) = sum from 1 to p-1 (i mod p) = (p-1)p/2 mod p = 0

(Just assume p != 2 cuz that's trivial)

[errant otter]

Aaaaaaa