elementary-number-theory

[sterile pumice]

Little Narwhal

[wise oyster]

okay and i think i got it for the even case

correct me if im wrong again

$g+p^e$ is odd so $(g+p^e)^{\phi(p^e)} \equiv 1 \mod 2$. Now if we can show that $g + p^e$ is a primitive root $\mod p^e$ we can apply the same method as for the odd case. To show this, we know that at least $(g+p^e)^{\phi(p^e)} \ equiv 1 \mod p^e$ by Euler's theorem. Now assume $(g+p^e)^k \ equiv 1 \mod p^e$. Then $g^k + p^e(...) \ equiv 1 \mod p^e$ iff $g^k \equiv 1 \mod p^e$. The smallest such k is $\phi(p^e)$ so the proof is complete.

[sterile pumice]

Little Narwhal

[wise oyster]

@keen furnace

lol yeah im stupid

yesterday broke me i think haha

thanks anyways

[wise oyster]

So I was trying to come up with another proof for showing that if $gcd(a,b) = 1$ then the biggest number that cannot be expressed as a linear combination of a and b with non negative coefficients is $n(a,b) = ab - a - b$ (frobenius number) and I think I got something but id love it if someone could corss check for mistakes

cross*

[leaden swan]

Sure

[wise oyster]

just to clarify, im only talking about the part of the proof where you show that numbers bigger than ab-a-b can be expressed as such a linear combination

the first part i did in a standard way i already knew

so

fuck

ive found a mistake

while rewriting it

and i dont think i can fix it ugh

[abstract flax]

:(

[wise oyster]

okay i mightve salvaged it

i have to rewrite everything though ugh

[wise oyster]

So an integer bigger than $ab-a-b$ is of the form $ab-a-b+m = ab-a-b+ax+by = a(b-1 + x) + b(y-1)$ (equation *)since a and b are coprime (x,y integers). Let's assume wlog that $x<0, y>0$. Then $y-1\geq 0$. If $b-1+x /geq 0$ we're done. If not, then $x \leq -b => x = -b-k$ for some natural k with $|k| < |x|$. Plugging that into m we get $m = -ab - ak + by = a(-k)+b(y-a)$ and so * becomes $a(b-1-k) + b(y-a-1)$. If $b-1-k \geq 0 , y-a-1 \geq 0$ then once again we're done. If $y-a-1 < 0$ Then $y = a - j$ for some natural j . Plugging into m we get $m = a(-k) + b(-j)$ which isnt possible since m is positive so $y - a -1 \geq 0$. So now let us assume $b-1-k < 0$ then $k > b-1$ and so $k \geq b => k = b + l$ for some natural l with |l|<|k|. Plugging into m yields $m = -ab-al +by -ba = a(-l) + b(y-2a)$. For * this gives $a(b-1-l) + b(y-2a-1)$. We can argue similarly as before that $y-2a-1\geq 0$ and so as we repeat this process the coefficient of a is b-1-g where g keeps decreasing in magnitude, so this process will eventually terminate such that both coefficients are positive.

I feel like it's a weird argument

lemme know if it's wrong

[sterile pumice]

Little Narwhal

[wise oyster]

at one point in the text there's a weird line that's supposed to read |l| < |k|

and the /geq is a mistake on my part i meant to write \geq in latex

[sacred junco]

First, observe that
$$
(2 n) !=2 n \cdot(2 n-1) \cdot(2 n-2) \cdots 3 \cdot 2 \cdot 1
$$
Of the $2 n$ terms in the right side of expression $(6.7), n$ of them are even, namely 2,4,6 $\ldots, 2 n .$ If we were to factor 2 from each of these numbers, we obtain $2^{n} \cdot 1 \cdot 2 \cdot 3 \cdots n=$ $2^{n} \cdot n !$, while the remaining $n$ integers, namely $1,3,5, \ldots, 2 n-1,$ are all odd. Thus
$$
(2 n) !=2^{n} \cdot n ! \cdot 1 \cdot 3 \cdot 5 \cdots(2 n-1)
$$

[sterile pumice]

LINEAR_ALGEBRA_GUY

[sacred junco]

How is it that they factor 2^n out and say the other terms are odd??? There are numbers like 8 which have multiple factors of 2.

2^n will only turn the numbers with one factor of 2 odd, not all even numbers

[sage fern]

so 1 -2- 3 -4- 5 -6- 7 -8-

there are 4 even numbers

can take a factor of two from each of them

then all the other numbers are odd

[sacred junco]

Yes

[sage fern]

that's all

[sacred junco]

I misread what they wrote

Sorry, my bad I didn't notice the n!

Thanks though

[sage fern]

np

[sleek cove]

wait

lineae alg guy is a weeb lmao

[sacred junco]

solve over the positive integers n^3+14n+14=k^2

i know here needs to take mod p but i dont know what p to take

i tried p =3 and p=7

i think im gonna try p=8

nope, dont work

...

p=9 maybe

[torn escarp]

p=3 is good

try it again and show me what you get

[sacred junco]

okay

if n congruent to 1 mod 3 dont work

i think now i need to show n cant be congruent with 1 mod 3 in this eq

[torn escarp]

not the strategy I had in mind

first reduce the entire equation mod 3, don't try to plug anything in yet

[sacred junco]

okay

k^2 can be congruent with 0 and 1 mod 3
now we need to prove LHS cant be congruent with 0 and 1 mod 3
n^3 + 14n + 14 is congruent to n^3+2n+2 mod3

[torn escarp]

there's a little more you can do

n^3=n mod 3

[sacred junco]

aaaaaaaaaaaaaaa

thanks a lot

[torn escarp]

yup

you're welcome

[lament relic]

there is a typo here right?

the "if and only if" part

because Carmichael numbers exist

[twin summit]

Yes

[leaden swan]

I think it's supposed to be "an integer is psuedoprime"

[sacred junco]

How do I prove this using induction: Let S ={i in Z | i ≥ 2}, and let P be a subset of S with the properties that 2,3 in P and if n in S, then either n in P or n = ab, where a,b in S. Then every element of S either belongs to P or can be expressed as a product of elements of P.

I started by doing a few bases cases, like 2 in S implies 2 in P, 3 in S implies 3 in P, 4 in S implies 4 = 2 * 2, and 2 is in P, 5 in S implies 5 in P

Then I tried to assume that $\exists k \in \mathbb{N}, \exists a,b \in P, (2 \in P \underline{\vee} 2 = ab)\land(3 \in P \underline{\vee} 3 = ab) \land \dots \land (k \in P \underline{\vee} k = ab)$

[sterile pumice]

LINEAR_ALGEBRA_GUY

[sacred junco]

For different a,b of course I just did bad notation

So then I tried to show that $\exists k + 1\in \mathbb{N}, \exists c,d \in P, k + 1 \in P \underline{\vee} k + 1 = cd$

[sterile pumice]

LINEAR_ALGEBRA_GUY

[sacred junco]

But I don't know where to go from here

[sacred junco]

<@&286206848099549185>

[swift shard]

This is the definition of P no? If something is not a product of elements in P, then it automatically belongs to P

[sacred junco]

@swift shard No that's what we're trying to prove

Hmm

[swift shard]

This is kind of like trying to prove all things are either true or false

(Which, let's just pretend we know they are)

[sacred junco]

So how can I finish the proof @swift shard or?

[swift shard]

Let's say X for all x ∈ N is true.

Base case, x = 0 is true.

Inductive step, assume x = n is true
Then x = n + 1 is true
Proven

I'm joking. The question is kinda broken though

Every element just being true doesn't really allow room for an induction

[sacred junco]

Why is it broken? Isn't it proving the fundamental theorem of arithmetic using induction?

[swift shard]

No. It's showing that every integer is a product of x ∈ P (is not in P) or is not a product of x ∈ P (is in P)

Showing that P is exactly the primes would be proving the fundamental theorem of arithmetic, but you aren't tasked with this

[sacred junco]

@swift shard my book says this is exactly that, except it's just implicitly proving it

[torn escarp]

if the sum of digits is divisible by 9, then the number is divisible by 9

good thing about this rule is you can chain it over and over again

just keep adding the digits together of the number you get until you get one that's obviously divisible by 9 or not

[leaden swan]

Or note 9 divides 10^k-1

[torn escarp]

oh I misread the question

I thought it was asking for what's an easy divisibility rule for 9 lol

[wise oyster]

I have an issue with the last step

suppose that k is odd

nvm

i found my answer

yet again

[manic arch]

$a=\sum a_i 10^i$ is divisible by 9 iff $a\equiv 0 \pmod 9$, and since $\sum a_i 10^i \equiv \sum a_i \pmod 9$ (as $10$ is $1\pmod 9$) we conclude that $a$ is divisible by 9 iff the sum of its digits is.

[sterile pumice]

derivada.schwarziana

[silk vine]

Ok so, I have heard that the proof that $\sum\limits_{k=1}^{n}\frac{1}{k}$ is never an integer for k>1 uses Bertrand's postulate somewhere.

But I don't really know how to use this result to prove it

Any ideas?

Also

Do I really need to use this result?

[red pewter]

The proof that what about that series

[silk vine]

Hmmm

[lusty hornet]

what do you want to prove with the harmonic series H_n ?

[silk vine]

Oh

For some reason I forgot to write the rest of the problem.

[sterile pumice]

MisterSystem

[silk vine]

k>1

[lusty hornet]

this https://math.stackexchange.com/questions/2746/is-there-an-elementary-proof-that-sum-limits-k-1n-frac1k-is-never-an-int#:~:text=If n>1 is an,by primes smaller than p.

other approaches also discussed there

@silk vine

[silk vine]

Yeah...

I don't really want to see any proofs of this result

Only some ideas of how to prove it.

But thanks

[lusty hornet]

I don't know if it is in one of the proofs there

But the easiest way I think, was I used to prove it by contradiction and Euclid's lemma

it was a really simple proof I did, in the end, I see my notes, I did use Bertrand's postulate. hmm!!

[silk vine]

Yey

I think I have a solution

[sacred junco]

Prove that if the real number r is a root of a polynomial with integer coefficients, then 2r is a root of a polynomial with integer coefficients.

I may be reading it wrong, but this seems like a false statement? For example, (x-1)^2 has root 1, for (2-1)^2 is not 0.

Or are they saying that there exists a polynomial with integer coefficients with a root 2r?

[silk vine]

Np, this is not a false statement.

Because the set of all real numbers that are root of a polynomial with integer coefficients has a really nice structure.

It's a field

And since 2 is an algebraic number, i.e it's the root of a polynomial with integer coefficients, then 2r should in fact be the root a polynomial with integer coefficients.

Because in general, if a is an algebraic number and b is also an algebraic number, then ab is an algebraic number.

[sacred junco]

@silk vine So I was reading it wrong then and they were saying that there exists a polynomial with a root(s) 2r

Because it's not true for every polynomial with integer coefficients and some root r

As I demonstrated

[silk vine]

[sacred junco]

Right ok

[silk vine]

Yeah, you were. But that's ok.

[sacred junco]

Well yeah that's obvious in that case

[torn escarp]

eh this just makes it that much harder though

because it uses facts that you haven't proven

you're essentially begging the question here

I'd go for something more direct, suppose n is the degree of the polynomial f(x) which has integer coefficients and has r as a root

then $g(x) = 2^n f(x/2)$ is a polynomial with integer coefficients and 2r as a root

[sterile pumice]

Merosity

[sacred junco]

Can someone confirm this works?

"If 8m + 1 is a perfect square for integer m, then m = n(n+1)/2 for n in N"

Assume that 8m + 1 is a perfect square, but there is no n in N for which m = n(n+1)/2. But observe that if m = 1, then 8 * 1 + 1 = 9, and when n = 1, then m = n(n+1)/2, so we have a contradiction

[leaden swan]

You can't substitute m=1

You are saying there's some m for which it's not of that form

You shouldn't specify m=1

[sacred junco]

But 8m + 1 is a perfect square

So it should work

This condition has to hold for all perfect squares

[sacred junco]

<@&286206848099549185>

[torn escarp]

how is there a contradiction?

9 is a perfect square

[sacred junco]

exactly, and if n = 1, then n(n+1)/2 = m

n is in N, but we said no such n would exist

[torn escarp]

oh the statement is "there is no n"

then that would work, I thought you were proving the opposite of that

[sacred junco]

I am proving this

"If 8m + 1 is a perfect square for integer m, then m = n(n+1)/2 for n in N"

However, going for the contradiction that no such n exists seemed easier

However, when I set m = 1, I found an n that works

[torn escarp]

that doesn't prove what you want then

[sacred junco]

Why?

[torn escarp]

you showed it holds for one case

[sacred junco]

Right, but we're assuming that no n exist at all when 8m + 1 is a perfect square

But I showed that an n does exist

[torn escarp]

this is just illogical

[lusty hornet]

you have found a single example where an implication is true, that doesn't mean it is proved

that also doesn't mean it is always true

[sacred junco]

I think it works. Look: $\forall m \in \mathbb{Z}, 8m + 1 = t^2 \implies \exists n \in \mathbb{N}, m = \frac{n(n+1)}{2}$

[sterile pumice]

LINEAR_ALGEBRA

[sacred junco]

Then notice that our contradiction would be

$\forall m \in \mathbb{Z}, 8m + 1 = t^2 \implies \forall n \in \mathbb{N}, m \neq \frac{n(n+1)}{2}$

[sterile pumice]

LINEAR_ALGEBRA

[sacred junco]

Yet, I showed a n for which m = that

I did the negation correctly of the consequent, right?

So my logic should hold

[lusty hornet]

nope negation of an implication p-> q is p AND ~ q

which is nowhere near what you wrote

[sacred junco]

@lusty hornet I'm not negating an implication.....

I am doing a proof by contradiction

@lusty hornet So what you wrote about is not relevant to what I did.

[torn escarp]

unrelated to this question, but the earlier one, did you end up reading my response?

MisterSystem's answer wasn't that good imo

[sacred junco]

Yes I did, I did it similarly to yours. I just wrote out the general form a polynomial, a1 + a2r + a3r^2 + ... + an+1r^n = 0

[lusty hornet]

then it is right

[sacred junco]

And then I multiplied by 2^n and factored it "inside" of the roots appropriately

And the leftover terms I combined with the a_i

[torn escarp]

cool

but back to this problem, this isn't right still

your proof by contradiction is broken somewhere

[sacred junco]

Do you agree that if we want to reach a contradiction, we assume that for all n in N, m ≠ n(n+1)/2?

[torn escarp]

because all you've done is show it holds for one case, that's not really sufficient to establish it

[sacred junco]

While 8m + 1 is a perfect square

I understand what you're saying, but the for all n in N is throwing me off

[torn escarp]

I could essentially redo your argument with something else that holds for just a single specific case and claim to have proved it

so obviously there's a flaw here

I would just not attempt to try to prove this by contradiction in the first place

[sacred junco]

Like we're showing what we assumed to be true for all n to be false for a specific n

Isn't that all we need?

[torn escarp]

I don't quite follow

[sacred junco]

We're assuming that for all n in N, m ≠ n(n+1)/2

That means I shouldn't be able to find a specific n that works

Do you agree?

But I was able to

[torn escarp]

I don't agree

[sacred junco]

[lusty hornet]

@sacred junco I will give you a hint, any odd perfect square is congruent to 1 mod8

work in this direction

[sacred junco]

Oh nevermind

I was making a silly logic mistake

My bad

@torn escarp How would you go about this anyway?

(I realized my mistake when I was typing up an analogy, and realized my analogy fails even though the situation is similar)

[torn escarp]

awesome

I think this is good, it's sort of like you taking the step from applying rules to really seeing how/why they're true as an extension of your own common sense reasoning

[sacred junco]

I fooled myself with the forall N

When I negated it

So that was a bad application of logic

[silk vine]

I really don't get why this argument holds

[silk vine]

Hmm

What did I say wrong?

I said what he was trying to prove was in fact true and that he didn't quite get the answer at first.

And yeah

Proving that the algebraic numbers is a field, or at least for the particular case of 2r is hard.

Yeah, but why are there φ(d) of them?

So what I am really counting is the number of fractions that can't be reduced any further by d?

[torn escarp]

@silk vine I say why where I gave my response

[silk vine]

You mean this?

Ok then cool

[torn escarp]

yup

[silk vine]

That's a neat solution to the problem tho

I don't quite get why this identity holds either

[vivid frost]

Geometric series formula

[silk vine]

Maybe this has to do with the expansion of log(1-p_i^(-1))

Oh

You are right

[sleek cove]

y math on phone

[sacred junco]

I think you should try writing down the proofs by yourself while reading maths books

I memorize them better and understand them better after that

[stuck lintel]

Newton sums

[sacred junco]

How do I prove that n^2 - 3n - 1 is never a divisor of 169, for any n in N?

I tried going the n odd, n even route, so n = 2k, so 4k^2 - 6k - 1, but that doesn't tell me much

I suspect a contradiction solution exists, but I don't know how

[vivid frost]

What are the divisors of 169?

[abstract flax]

I can think of 2, 1 and 169

[vivid frost]

13

[abstract flax]

Oh wow

What's 13^2?

[vivid frost]

So you just have to prove it doesn't have solutions for any of these

[abstract flax]

Oh, I thought you were asking. Didn't see context of previous question

[vivid frost]

Lmao

[torn escarp]

kek

[torn escarp]

since you want this to be a divisor of 169, you should be looking at it mod 169, not mod 2 (odd or even)

for it to be a divisor of 169 we'll have n^2-3n-1=0 mod 169

now since 169=13^2 we can make our lives a little easier to break it up into steps, since for this to be 0 mod 169 it must also be 0 mod 13 which is much easier to check

you can then check all 13 cases by hand pretty easily and luckily you'll find only n=8 works mod 13

then to go back up to mod 169 case we take n = 8 + 13*m to be our next step up

then because m already is multiplying 13, you only have 13 possibilities for m

think of this as getting the base 13 expansion of the number n

well, maybe don't if that sounds confusing, the main thing is we don't have that many cases to check lol

[vivid frost]

Or you could always just use the quadratic formula

[torn escarp]

yeah but then how would we torture children?

[torn escarp]

@sacred junco here if you use the quadratic formula you have to tell me what's wrong with this proof that n^2+1 is never a divisor of 169, for any n in N. We look at n^2+1=0 mod 169 and since by the quadratic formula n=i or -i then because it's not a real number it can't work.

[sacred junco]

Well, I mean it seems fine but I haven't really done modular arithmetic with imaginary numbers so I am not sure what to tell you lol

@sleek cove ?

[sleek cove]

he just said it cant work for i

[sacred junco]

He said "what's wrong this proof"

[torn escarp]

n^2+1 is divisible by 169 for infinitely many integers

seems like you've missed the point of all this, did you read what came before this?

[sacred junco]

I know that, but why does the proof fail for imaginary numbers?

[torn escarp]

it's not about imaginary numbers, it's about what numbers have square roots

n^2-2 = 0 mod 5 also has no solutions but isn't imaginary, it's because there's no square root of 2

to give a non imaginary example

[sacred junco]

Oh good point

Now I get it thanks 🙂

@torn escarp But I think you got the original problem backwards

We wanted to show n^2 - 3n - 1 is not a divisor of 169

Not that 169 is not a divisor of n^2 - 3n - 1

Or else I am misunderstanding why you wrote mod 169

[torn escarp]

I wrote mod 169 because the original problem was mod 169

[sacred junco]

But wouldn't it be 169 = 0 mod (n^2 - 3n - 1)

[torn escarp]

lmao

does seem that way

[sacred junco]

[torn escarp]

haha I must have been tired and trigger happy to think to use hensel's lemma

the way I'd do it now is we're just trying to find an n so that $n^2 -3n-1 =13^k$ to be a divisor of 169, it has to be for k=0,1,2

[sterile pumice]

Merosity

[torn escarp]

so look at the discriminant mod 3

$9+4(13^k+1) \equiv 2 \mod 3$ and all squares are 0 or 1 mod 3, so it can't be a square, done

[sterile pumice]

Merosity

[sacred junco]

Ok that is pretty clean

[torn escarp]

had to redeem myself lol

[sacred junco]

It's ok you already got sullied

And that second proof is very nice

[sacred junco]

when m-n divides m+n

an example, when divides
(10x+y) -24 divides (10x+y)+24

[dense hawk]

this is a dumb question but how would someone find which integer values of k satisfy 11 divides (4k+1)

[torn escarp]

if 11 divides 4k+1 then it means 4k+1 = 0 mod 11

and you can solve for what k has to be mod 11

[dense hawk]

how

[torn escarp]

how in what sense

[dense hawk]

meh so 4k is equivalent to 10 mod 11

which means 2k is equivalent to 5 mod 11 because 2 and 11 are relatively prime

which means 2k is equivalent to -6 mod 11 or 2k+6 is equivalent to 0 mod 11 or 2(k+3) is equivalent to 0 mod 11 which tells us that k+3 is equivalent to 0 mod 11 or k is equivalent to 8 mod 11 so k=11n+8. did i do that right?

[sacred junco]

How do I prove that $a_2 = 1 + \frac{1}{2}, a_n = a_{n-1} + \frac{1}{n}$ for $n \ge 3$ is never an integer?

[sterile pumice]

LINEAR_ALGEBRA

[manic arch]

yep seems right to me

[abstract flax]

Hahahaha

@agile elk #multivariable-calculus is the channel you were told to move to. This does not belong here.

[agile elk]

XD sorry again misinterpreted the message

[abstract flax]

Np, np

[sacred junco]

If a, b, c are any three distinct positive integers such that 1/a + 1/b + 1/c = 1, then a + b + c is a prime

rip

[twin summit]

not really, consider 1/a>1/b>1/c, then 1/c+1/c+1/c =1 \implies c=3, so 1/a>1/3, since a is an integer, a=2. Then 1/b+1/c=1/2, now consider the same thing again 1/b>1/4 , so b=3, and c=6. Hence a+b+c=11 which is prime

[sacred junco]

@twin summit Yeah it's ok I got it

Thanks

[inland silo]

We have right to do this ?
5x ≡ 9 [mod 12]
5x * 5 ≡ 9 * 5[mod 12]
25x ≡ 45 [mod 12]
25x - 12 - 12 ≡ 45 - 12 - 12 - 12 [mod 12]
x ≡ 9 [mod 12]

[twin summit]

I got lost in 2nd last step

[inland silo]

why ?

[sacred junco]

yeah it's good

[inland silo]

For the 2nd
10x ≡ 6 [mod 14]
10x + 14y = 6
5x + 7y = 3

5x * 3 ≡ 3*3 [mod 7]
15x - 7 - 7 ≡ 9 - 7 [mod 7]
x ≡ 2 [mod 7 ]

but weird

I thought we had to use the euclidean algorithm to solve this type of question and in fact not

[inland silo]

but if you withdraw 3 times -12 on the left you can withdraw 4 times -12 on the right? it shouldn't be 3 times -12 on the left and 3 times -12 on the right like for multiplication?

[sacred junco]

but if you withdraw 3 times -12 on the left you can withdraw 4 times -12 on the right?
yes you can

[inland silo]

Because Username said he got lost

[sacred junco]

nvm he dm'd me I explained to him

[twin summit]

ah sorry I got confused too since I mostly dealt with multiplication too

[inland silo]

Ok and to answer equations like that you never need the Euclidean algorithm? because my teacher tells me to solve with the euclidean algorithm but we didn't need to use it here

[leaden swan]

Euclidean algorithm is an algorithm to find the inverse

[inland silo]

But isn't it useful for that kind of question? because all we did was basic operations

[leaden swan]

It makes your life easier

[inland silo]

It takes a lot longer

When you don't need to use it you save a lot of time

[brazen python]

could someone briefly explain this please? i'm kinda stuck

[brazen python]

yes

oh ok

so since a|b and a|c then a|bx and a|cy is also true

yeah

by which rule are you allowed to combine those 2 tho

if that makes sense

right

oh i see

makes sense

thanks :)

[sleek cove]

you're welcome

[inland silo]

Hi, I'm posting the questions I couldn't answer today, I'm going to go to sleep, if you can explain to me in detail, I'll read tomorrow

1. Determine the possible values ​​of x ^ 12 [mod 7] , x ^ 12 [mod 13] , x ^ 12 [mod 91] for x ∈ Z
2. Determine all the possible values ​​of x^ 36 [mod 999]
3. Solve the congruence x ^ 40 ≡ x ^ 4 [mod 999]
4. Determine the number of solutions [mod 8] of the congruence x² ≡ 1 [mod 8]. Same thing for x² ≡ 1 [mod 9] and x² ≡ 1 [mod 72]
   There you are, these are independent questions, but very similar to each other. If you can explain to me for one or two / or better show me. So that I can redo.
   Thanks a lot, see you tomorrow

[sleek cove]

see where you can apply fermats little theorem

[wise oyster]

For the first one note as well that 91=7*13 so youll be able to recombine the residues of the first two congruences. For the third i feel like there must be someway to invert x^4 mod 999 so you get a special case of question2. For the last one use theorems on quadratic residues

[sleek cove]

u know what i meant

[inland silo]

Someone can help me ?

[sleek cove]

[inland silo]

I've been on this for 2 hours, my brain wants to burn, please

[sleek cove]

do u need more help

[inland silo]

The question is : find all values possible of x^(12) [mod 91]

What I do :

At the beginning I had x^(12) [mod 91]I decompose this into a system of two equations
{ x^(12) [mod 7]
{ x^(12) [mod 13]
And after this, I used the Euler's theorem
to get this
{ x^(7-1) ≡ 1 [mod 7]
{ x^(13-1) ≡ 1 [mod 13]
Finally, we find what I gave
{ x^(6)² ≡ 1² [mod 7]
{ x^(12) ≡ 1 [mod 13]
and
{ x^(12) ≡ 1 [mod 7]
{ x^(12) ≡ 1 [mod 13]
So to get this form I have already used Euler's theorem

case where x ^n: is not prime with 7 or 13 (or 7 but not 13 or 13 but not 7)
{ x^(12) ≡ 0 [mod 7]
{ x^(12) ≡ 0 [mod 13]
{ x^(12) ≡ 0 [mod 7]
{ x^(12) ≡ 1 [mod 13]
{ x^(12) ≡ 1 [mod 7]
{ x^(12) ≡ 0 [mod 13]

After doing all of this, what should I do?

Sideurk?

.. 😞

[wise oyster]

Chinese remainder theorem to combine solutions. Let y be x^12 you have y = 0 or 1 mod 7 and y = 0 or 1 mod 13. N1 = 13, N2 = 7. Invert 13 mod 7 to get H1=6 mod and invert 7 mod 13 to get H2 = 2. So y = (0 or 1)136 + (0 or 1)72 = (0 or 1)78 + (0 or 1)14 mod 91. So y = 1 mod 91 if both are 1, y = 0 mod 91 if both are zero which was obvious anyways, y = -13 mod 91 if y = 1 mod 7 and y = 14 mod 91 if y = 1 mod 13.

[regal aspen]

Wait LMAO

hahhahahahaha

That's so sad that you had to do all this bashing for that

By fermat's last theorem, a^(p-1) is 1 mod p as long as p doesn't divide a. So basically, x^12 is either 1 or 0 mod 7 cause a^p-1 for 7 would be a^6, so a^12 would also be 1 mod 7. For 13, p-1 = 12 so directly we can say that x^12 must be 1,0 mod 7,13. Then you can continue as Narwhal said

[wise oyster]

That's literally what they did what's your point...

[regal aspen]

Wait they did?

Why so many cases then

Should have been a one liner?

[wise oyster]

They were making sure to write out all the cases separately and clearly

Next time bother reading and dont mock the work of the person asking for help

[regal aspen]

you're right

I'm just a little tired

Sorry dude

[wise oyster]

Np, i was a little harsh too apologies

[regal aspen]

nah nah

It was disrespectful

completely my bad

[inland silo]

But I don't see how to use the Chinese remainder theorem here

In my case

for

{ x^(12) ≡ 0 [mod 7]
{ x^(12) ≡ 0 [mod 13]

so if you say x^(12) = y

{ y ≡ 0 [mod 7]
{ y ≡ 0 [mod 13]

and here a_1 = 0 and a_2 = 0, like on my screen. So we found nothing : ** y = 0 [Mod 91]**

{ x^(12) ≡ 0 [mod 7]
{ x^(12) ≡ 1 [mod 13]

{ y ≡ 0 [mod 7]
{ y ≡ 1 [mod 13]

in thise case

I have N_1 = 13, N_2 = 7, n_1 = 7, n_2 = 13, a_1 = 0, a_2 = 1

So x = u_1 * a_1 * N_1 + u_2 * a_2 * N_2 [Mod N]

So for gcd(13,7), so 13u + 7v = 1

I find u_1 = 1

for gcd(7, 13), I find u_2 = - 1

so ** y = 1 * 0 * 13 - 1 * 7 * 1 [Mod 91]**

y = - 7 [Mod 91]

{ x^(12) ≡ 1 [mod 7]
{ x^(12) ≡ 0 [mod 13]
{ y ≡ 1 [mod 7]
{ y ≡ 0 [mod 13]

In thise case we found :

y = 13 [Mod 91]

on this case :

{ x^(12) ≡ 1 [mod 13]
{ x^(12) ≡ 1 [mod 7]

{ y ≡ 1 [mod 7]
{ y ≡ 1 [mod 13]

y = 1 * 1 * 13 - 1 * 1 * 7 [Mod 91] so y = 6 [Mod 91]

So for my three system by applying the Chinese theorem, by setting y = x ^ (12) as you told me, I find

y = 0 [Mod 91] and y = - 7 [Mod 91] and y = 13 [Mod 91] and y = 6 [Mod 91]

It's a little different than what you find Narwhal, why ?
I solved the four systems, one by one, using the Chinese Remainder Theorem

[wise oyster]

first of all for the case x^12 = 1 mod 7, x^12 = 0 mod 13 i said x^12 = -13 mod 91, not 13. Second, youve calculated your inverses mod n wrong, im not sure how since you havent showed me how you calculated them, but your u values are wrong. You can find confirmation of my results on an online calculator if you arent confident

The inverse of 13 mod 7 is 6

because 6*13 = 78 = 77 + 1

you could more simply also find that it is -1

since -1 * 13 = -13 = -14 + 1

-1 = 6 mod 7 so it checks out

as for the inverse of 7 mod 13

that's easily seen to be 2

so your u1 is -1 or 6 and your u2 is 2

and then you can just do the thing

@inland silo

[inland silo]

I will develop what I said. In the 4 systems I wrote I applied the Chinese Remainder Theorem

{ y ≡ 0 [mod 7]
{ y ≡ 0 [mod 13]

{ y ≡ 1 [mod 7]
{ y ≡ 1 [mod 13]

{ y ≡ 0 [mod 7]
{ y ≡ 1 [mod 13]

{ y ≡ 1 [mod 7]
{ y ≡ 0 [mod 13]

In all these cases, we have N = 7 * 13 = 91 , we have N_1 = 13 and N_2 = 7

We have, also n_1 = 7 and n_2 = 13. There are only a_1 and a_2 which change depending on the systems

So that for the 4 cases, we obtain a final result which is:

x = u_1 * a_1 * N_1 +u_2 * a_2 * N2 [Mod N]

For this case :

{ y ≡ 1 [mod 7]
{ y ≡ 0 [mod 13]

We have a_1 = 1 and a_2 = 0

According to Bezout's theorem there exists (u, v) ∈ Z² such that 13u + 7v = 1

pgcd(13, 7) = 1 and with Euclid's algorithm :

13 = 7 * 1 + 6

7 = 6 * 1 + 1

By going up this algorithm, one obtains successively:
6 = 13 - 7 * 1

1 = 7 - 6 * 1

so 1 = 7 - (13 - 7) which ultimately gives: 13 * (-1) + 7 *( 2) = 1
So our u_1 for the system { y ≡ 1 [mod 7] and { y ≡ 0 [mod 13] is u_1 = - 1

What the online emulator confirms :

and u_2 there is no need because on the equation x = u_1 * a_1 * N_1 +u_2 * a_2 * N_2 [Mod N] a_2 = 0 for my first case system

So according to the Chinese remainder theorem for this first case, we have
x = (-1) * 1 * 13 [Mod 91] = - 13 [Mod 91]

And my other cases have followed the same reasoning as this one. So I don't understand why this is wrong, because I applied the theorem very well (At least I think.)

For the 2nd case

{ y ≡ 0 [mod 7]
{ y ≡ 1 [mod 13]

We have a_1 = 0 and a_2 = 1

u_1 there is no need because on the equation y = u_1 * a_1 * N_1 +u_2 * a_2 * N_2 [Mod N] a_1 = 0 for my 2nd case system

Here we have u_2 = 2

y = 1 * 2 * 7 [Mod 91] so we have y = 14 [ Mod 91]

So to recap the four systems

For

{ y ≡ 1 [mod 7]
{ y ≡ 0 [mod 13]

we have u_1 = -1 so ** y = (-1) * 1 * 13 [Mod 91] = - 13 [Mod 91]**

For

{ y ≡ 0 [mod 7]
{ y ≡ 1 [mod 13]

we have u_2 = 2 so y = 1 * 2 * 7 [Mod 91] = 14 [Mod 91]

For

{ y ≡ 0 [mod 7]
{ y ≡ 0 [mod 13]

**we have y = 0 [Mod 91] ** because a_1 = 0 and a_2 = 0 and we have the equation y = u_1 * a_1 * N_1 +u_2 * a_2 * N_2 [Mod N]

For
{ y ≡ 1 [mod 7]
{ y ≡ 1 [mod 13]

y = (-1) * 1 * 13 + 1 * 2 * 7 [Mod 91] = 1 [Mod 91]

@wise oyster

Sorry Narwhal x)) I really need help with this

[wise oyster]

yes now this is correct

it's as i told you

you end up with y = 0 mod 91, y = -13 mod 91, y = 14 mod 91, or y=1 mod 91

and so you're done

@inland silo what else do you need help with?

[inland silo]

Ok thank you very much really

Well, I'll repost it here

Exercice : Find b ∈ {0, ..., 142} such that 2020 ^ (2019) = b [mod 143]
143 = 13 * 11
I write this in a system of two equations
{ 2020^(2019) ≡ b [mod 11]
{2020^(2019) ≡ b [mod 13]
We can also say
{7^(2019) ≡ b [mod 11]
{5^(2019) ≡ b [mod 13]
Using the little fermat theorem :
{7^(10) ≡ 1 [mod 11]
{5^(12) ≡ 1 [mod 13]
I need help from there

[wise oyster]

so reduce 2019 mod 10 to get 7^9 = b mod 11 and reduce 2019 mod 12 to get 5^3 = b mod 13

compute 7^9 and 5^3

[small coral]

uh i was typing in the other channel

ig ill put it here then

[wise oyster]

and reduce them mod 11 and mod 13 respectively

[small coral]

yeah so to reduce 7^9 u dont have to compute the whole thing

[wise oyster]

well it's easier to compute (-4)^9

[small coral]

u can write it as 343^3 and note that 341 is divisible by 11 so 343 can be reduced to 2

[torn escarp]

@inland silo don't cross post your questions

[small coral]

so its just 2^3=8 mod 11

[wise oyster]

that works too

and is a lot better haha

[small coral]

yeah so basically convenient stuff happens with the 5^3 also

youll find that 5^3=125 is 5 less than a multiple of 13 so its congruent to 8 mod 13

so u have that the big number is congruent to 8 mod 11 and 8 mod 13

[inland silo]

i think I write on a sheet I come back

[inland silo]

oK
I have
{2020^(2019) ≡ b [mod 11]
{2020^(2019) ≡ b [mod 13]
{7^(2019) ≡ b [mod 11]
{5^(2019) ≡ b [mod 13]
{7^(10) ≡ 1 [mod 11]
{5^(12) ≡ 1 [mod 13]
From there I write
7^(2019) = 7^(2020) * 7^(-1) = (7^(10))^(202) * 7^(-1)
5^(2019) = 5^(2016) * 5^(3) = (5^(12))^(168) * 5^(3)
Now
{ (7^(10))^(202) * 7^(-1) ≡ 1^(202) * 7^(-1) [mod 11]
{ (5^(12))^(168) * 5^(3) ≡ 1^(168) * 5^(3) [mod 13]
We simplify as
{ (7^(2019) ≡ 7^(-1) [mod 11]
{ (5^(2019) ≡ 5^(3) [mod 13]

It's good?

[small coral]

yeah but 7^-1 is 1/7

or in this case its the inverse of 7 mod 11

u can think of it as 7^9 instead of 7^-1

and then 7^9=343^3 which is congruent to 2^3 or 8 mod 11

or if u want to do the inverse stuff u can say that 7^9=x mod 11, 7^10=7x=1 mod 11, so we have 7x=1 mod 11, then add 11 to 1 until u get a multiple of 7 (which happens to be 5 times) so 7x=56 mod 11 and x=8 mod 11 (you dont have to divide the 11 by anything because 7 and 11 are relatively prime)

either way you get the same result

[inland silo]

so

{ (7^(2019) ≡ 2^(3) [mod 11]
{ (5^(2019) ≡ 5^(3) [mod 13]

and finally

{ (7^(2019) ≡ 8 [mod 11]
{ (5^(2019) ≡ 125 [mod 13]

and finally

{ (7^(2019) ≡ 8 [mod 11]
{ (5^(2019) ≡ 8 [mod 13]

, And now to get to this step, I can use the Chinese Remainder Theorem, Or in fact, not really because the term on the left is not identical ...

Otherwise I was going to put y = ... ^ (2019) and solve for each case

but 7^(2019) and 5^(2019) it's not same, so I can't put this y

[small coral]

yes but remember that 7^2019 was originally 2020^2019

so we have 2020^2019=8 mod 11 and 2020^2019=8 mod 13

so then u can use crt to find that 2020^2019=8 mod 143

[inland silo]

Ok so

{ (2020^(2019) ≡ 8 [mod 11]
{ 2020^(2019) ≡ 8 [mod 13]

And I can put y = 2020^(2019), to solve :

{ y ≡ 8 [mod 11]
{ y ≡ 8 [mod 13]

and according to the Chinese Theorem, N = 11 * 13 = 143 , N_1 = 13 and N_2 = 11

And n_1 = 11, n_2 = 13 and a_1 = 8, a_2 = 8

y = u_1 * a_1 * N_1 +u_2 * a_2 * N_2 [Mod N]

y = u_1 * 8 * 13 +u_2 * 8 * 11 [Mod 143]

pgcd(13, 11) = 1

u_1 = -5 and u_2 = 6

then ** y = 5 * 8 * 13 + 6 * 8 * 11 [Mod 143]**

so, y = 1048 [Mod 143] = 43 [Mod 143]

@small coral the final result, it's good ? And there is no other case to study?

y = 43 [Mod 143]

[small coral]

isnt it just 8 mod 143

because 8 mod 13 and 8 mod 11

so its 8 more than a multiple of 11 and 8 more than a multiple of 13, meaning its 8 more than a multiple of both 11 and 13 meaning its 8 more that a multiple of 143 meaning its congruent to 8 mod 143

[inland silo]

So that gives me 5 systems of equations to solve?

[small coral]

wha

which systems lol

wasnt the question just what is 2020^2019 congruent to mod 143

[inland silo]

Ahhh so it’s not that

y = 43 [Mod 143]

It’s just that

2020^2019=8 mod 143

Because you told me to apply the crt but when I apply the crt I find y = 43 [Mod 143]

anyway thank you very much for your help i managed to do something in 2 hour what i tried to do in 10 on my own. It's hard to get help without having a little more than a sentence especially when you're having difficulty. So thanks @small coral and @wise oyster

Have a good Night

[small coral]

np

[sleek cove]

ok

[inland silo]

what ?

[inland silo]

Determine all possible values ​​of congruence x^36 [mod 999]

What I do :

I decompose 999 = 3 ^ 3 * 37

{x^36 (mod 37)
{x^36 (mod 27)

According to the little fermat theorem :

{x^26 = 1 (mod 27) if x prime with 27
{x^36 = 1 (mod 37) if x prime with 37

For the first equation, we have the following formula : φ(p^k)=p^{k-1}(p-1)

Here, p = 3 and k = 3, so φ(3^3) = 3^{3-1} * (3 -1) = 3² * 2 = 18

So by Euler's theorem, if x is prime with 27, x ^ 18 = 1, then

{x^(18)² = 1² (mod 27) if x prime with 27
{x^36 = 1 (mod 37) if x prime with 37

{x^36 = 1 (mod 27) if x prime with 27
{x^36 = 1 (mod 37) if x prime with 37

According to the Chinese remainder theorem
N = 37 * 27 = 999

N_1 = 37

N_2 = 27

n_1 = 27

n_2 = 37

and a_1 = 1 and a_2 = 1

We put y = x^36 and we want u_1 and u_2 as

y = u_1 * a_1 * N_1 +u_2 * a_2 * N_2 [Mod N]

y = u_1 * 1 * 37 +u_2 * 1 * 27 [Mod N]

pgcd(37, 27) = 1

u_1 = - 8

u_2 = 11

y = - 8 * 1 * 37 + 11 * 1 * 27 [Mod 999]
y = 1 [mod 999]

FOR

{x^36 = 0 (mod 27) if x not prime with 27
{x^36 = 0 (mod 37) if x not prime with 37

y = 0 [Mod 999]

For

{x^36 = 1 (mod 27) if x prime with 27
{x^36 = 0 (mod 37) if x not prime with 37

y = - 296 [Mod 999]
y = 703 [Mod 999]

For
{x^36 = 0 (mod 27) if x not prime with 27
{x^36 = 1 (mod 37) if x prime with 37

y = 297 [mod 999]

So we have, y = 1 [mod 999] and y = 0 [Mod 999] and y = 703 [Mod 999] and y = 297 [mod 999] as all possible values ​​of congruence x^36 [mod 999]

it's good ?

[inland silo]

after they ask to solve the congruence x^40 = x^4 [Mod 999]

I use the 4 system of equations that I put above?

{x^36 * x^4 = 0 (mod 27) if x not prime with 27
{x^36 * x^4 = 0 (mod 37) if x not prime with 37

{x^36 * x^4 = x^4 (mod 27) if x prime with 27
{x^36 *x^4 = x^4 (mod 37) if x prime with 37

{x^36 * x^4 = x^4 (mod 27) if x prime with 27
{x^36 * x^4 = 0 (mod 37) if x not prime with 37

but after done that, what do I do?

[sacred junco]

[faint turtle]

Ah yes.

[inland silo]

It’s really disrespectful to me. And I do not understand the purpose of these interventions

[sacred junco]

[worthy nimbus]

@inland siloI know mathematicians aren't usually the patient type, but exercising some patience would be good here. No one is obligated to provide to you a detailed response and think through your problem. Likewise, becoming furious over trivial matters will only make it more difficult to receive said help.

[timid olive]

[inland silo]

Which report ? I'm not talking about that. You didn't understand the problem I am very patient but every time I post a message there are the same people who answer under my message each time with or or "yes, ahok"

Are you going to tell me it's not about me?

[civic elk]

Sideurk posted this comment 3 days ago and he hasn't even commented now

I get it, please don't post offtopic in these channels fellas

but also, please chill out mate. Those comments weren't discussion derailing it was singular messages.

[inland silo]

Not only 3 days ago, he reacted to my message I just deleted my first message so his reaction was deleted

[civic elk]

I just don't see why this is so upsetting when you have a long discussion with someone and then a single message at the end by an unrelated party is so significant

[inland silo]

If I hadn't posted anything here there wouldn't be these people doing this here . What do they want from me? Nothing to do with asking for help. I just don't understand how you can say that it's not about my posts that they do this

[civic elk]

Okay but you can just ignore it too. Here, I'm saying it now: don't post off-topic comments in this channel.

I'm also going to stop talking now because I would be contradicting myself :~)

[inland silo]

I am preparing a very important exam for my future. Who is in a few days. I do exercises in a section which is mathematics #elementary-number-theory and not #chill . I try to make an effort and I don't force anyone to help me but why react like this to my messages?
Would you like us to do this for you? Talking about a serious subject and someone not taking you seriously by reacting a few hours later like that?
In my culture it's disrespectful

[civic elk]

As I said before, singular message. One post. Not discussion derailing, the type of thing you should ignore instead of taking it personally.

[karmic crest]

probably missing something easy with this one, (part c) any odd number that's the sum of 2 primes is 2 + an odd prime, so you're supposed to count the number of odd primes <= x - 2 basically? That's at most (x - 2)/3 + 2 - 1 (getting rid of 1) + 1 (adding back in 3) from part (b), but that only gets you at most x/3 + 4/3, and their bound is looser than that so feel like I've missed something

[karmic crest]

testing for a few small x, x/3 + 4/3 seems ok but 4/3 < 4 would seem unnecessarily loose (over like 4/3 < 2)

[karmic crest]

anyone? lol

[near hedge]

Is the Riemann hypothesis true or false?

[sage fern]

yes

[leaden swan]

What if it's not true or not false?

[near hedge]

What do you mean? It is either true, and we are correct, based on all assertions, or we are wrong, and something else is true? Please elaborate

[leaden swan]

See fuzzy logic

[spare garden]

hey number theorists, basic question here

https://math.stackexchange.com/questions/1527475/prove-perfect-square-of-the-form-4k-or-4k1

[leaden swan]

What's the problem?

[spare garden]

Hello moonbears, yes the problem is was there any way to tell before calculating it that only the even and odd cases were necessary

[leaden swan]

All numbers are either even or odd

Follows from euclidean lemma

[spare garden]

For example, I am working on a problem that does a similar thing for cubes, and for cubes you must use 3 forms

3k , 3k + 1, and 3k+2

[leaden swan]

Well,It depends on the problem

Sometimes you want remainders modulo 7

Like 7 cases: 7k,7k+1,...7k+6

[spare garden]

ah sorry, it's modulo 9

as in we want to prove a cube is only of the form 9k, 9k + 1 , 9k + 8

we use 3k, 3k+1,3k+2 to do so

I originally attemped the problem using just 2k,2k+1 and failed

[leaden swan]

Well, Just do 9 cases,and then try to see if any of them are identical

(9k+1),(9k+4) and (9k+7) will behave identically

So,You can just group thrm as (3k+1)

[spare garden]

is there a trick for seeing how those are the same

I'm trying to calculate it out now

[torn escarp]

it's sorta a special case cause the exponent 3 in mod 3^2 will give you an extra 3

[leaden swan]

9 divides (a+3)^3-a^3

[torn escarp]

maybe I'm not helping by saying that, don't let me derail you lol

[leaden swan]

So,cubes of (9a+1) ,(9a+4),(9a+7) leave the same remainder when divided by 9

Similary for (9a),(9a+3) and (9a+6)

[spare garden]

sorry I'm, not following where this comes from

[leaden swan]

Binomial expansion

(a+3)^3=a^3 +9 a^2 + 27 a +27

(a+3)^3-a^3=9(a^2+3a+3)

[spare garden]

okay nice

[torn escarp]

if you want to be a little more extreme we can say $a^{p^n}=b^{p^n} \mod p^n$ when $a=b \mod p$

[sterile pumice]

Merosity

[torn escarp]

which b=a+3 is mod 3

[spare garden]

I'm still trying to connect tge binomial expansion to everything else

So every term in (9a+1) ^ 3,(9a+4)^3,(9a+7)^3 is going to be multiplied by 9

except for the last one, respetivly, 1^3 , 4^3 , 7^3

that is where merositys theorem comes in to prove 1^3 = 1 mod 3, 4^3 = 1 mod 3, and 7^3 = 1 mod 3

[torn escarp]

hold up looks like you're going backwards in a sense

it's 3a, 1+3a, 2+3a that are being cubed

"my theorem" is a generalization of doing the same binomial expansion stuff moonbears-d- is doing

so don't listen to me, I was just saying extra noise for extra credit to think about later lol

[sacred junco]

I'm a little lost on how to solve this problem, I know that - (1 + ...) is a series that converges but don't know where to go from there

[sleek cove]

do you know what it converges too?

[sacred junco]

I don't remember how you can do that for this particular series

[sleek cove]

it converges to e

[sacred junco]

can I ask how you calculated that?

[sleek cove]

well there are many proofs

you can just use the taylor series for e^x, with x = 1. unless you want to use the definition of e which is annoying

[oblique barn]

use Taylor series of e^x centered at 0

[sacred junco]

find positive integers such that (2x)^4-y^2=2024

with factorize is to much work

,i tried something

y is even implies exists k positive integers such thah y=2k

we substitute

and k is even implies k =2p, p is a positive integers

we substitute again

and LHS is congruent to 0 mod 4 and RHS is congruent to 2 mod4

is correct?

[sage fern]

i am very tired

yeah, it looks like they can't exist

[spare tangle]

Asking in this channel because this is the first Number Theory module I've encountered at university and the concepts still seem quite elementary. Does anyone know any free PDF resources or videos for this module? My lecturer gives 5-15 minute lectures (way too brief, lacking examples and too fast paced etc) and the consensus is that she lacks clarity in her teaching :/ Here is the syllabus: https://www.ucl.ac.uk/maths/sites/maths/files/math0034.pdf

[regal aspen]

@sacred junco yup 🙂

[sacred junco]

thanks!

[torn escarp]

Look at it mod 16 and you have y^2 = 8*stuff mod 16 which is impossible because y^2 can't have a 3rd power of 2.

maybe I'm biased but to me this seems more obvious from the perspective of the 2-adic absolute value and the ultrametric equality, since $|(2x)^4|_2 \le 2^{-4}$ and $|2024|_2 = 2^{-3}$ we have $$|y^2|_2 = |(2x)^4-2024|_2 =\max(|(2x)^4|_2,|2024|_2)= 2^{-3}$$ at this point it's more clear that $|y|_2^2 = 2^{-3}$ has no solutions since the power on $y$ is even, which is effectively the same argument as reasoning mod 16

[sterile pumice]

Merosity

[paper lion]

Burton's book is on your reading list, and I second that. It covers much more than your curriculum, and is suited to self study. I'm not entirely sure of a good lecture series on elementary number theory, but you should be able to find specific tid-bits on YouTube(searching with the exact topic name might turn up some results).

[spare tangle]

Thank you 🙂

[sacred junco]

Thanks a lot

[torn escarp]

you're welcome

[sacred junco]

first digit of 5^{30} is?

[paper lion]

You should be able to deduce some pattern. 5, 25, 625, something starting with 3, then 1, then 5, 2, 6, ...

[sacred junco]

Thanks

[spare tangle]

I don't understand why the highlighted portion is true and to be honest, I'm not sure what a congruence "class" means either. I understand that the there's a congruence symbol and I'm a little confused about how I'm meant to interpret this symbol as it used to mean something else when we were studying different areas of Mathematics?

Kindly tag/mention/ping me if replying since I keep notifications off, thanks in advance ❤️

[abstract flax]

@spare tangle

$\overline{x}$ just means the equivalence class of x. Now if you look at the equivalence class of 0 there, you see that 3 is in it. So the equivalence class of 3 is also the equivalence class of 0.

[sterile pumice]

Lunasong

[spare tangle]

Sorry for the late reply, how do we know the equivalence classes of 3 and 0?

ahh I see what's going on

I missed this definition 😅

Thank you so much

[sleek cove]

you're welcome

[spare tangle]

I'm not sure if this is number theory

However, to answer your question, it is most certainly a function (I hope I don't need to explain why), and all functions are relations, therefore D

@tepid jungle

[grave carbon]

To prove

$$gcd(a,b)=1 \land gcd(a,c)=1 \implies gcd(a,bc)=1?$$

Would it suffice to just use the definition of gcd, then use that to derive 1 divides bc? Or would I also have to prove that 1 is the greatest integer that divides bc?

[sterile pumice]

beeswax

[grave carbon]

Say this was my proof:

Let a,b,c $\in \mathbb{Z}$ Assume gcd(a,b)=1 and gcd(a,c)=1. Then $\exists r,s,t \in \mathbb{Z}$ such that
$$1r=a, 1s=b, 1t=c$$ and that 1 is the greatest integer that divides a,b,c. Clearly, 1 divides a. Also,
$$bc = st = 1(st)$$ Therefore, gcd(a,bc) = 1. $\blacksquare$

[sterile pumice]

beeswax

[grave carbon]

Would this suffice?

[sleek cove]

all youve really shown is bc=bc

[grave carbon]

Oops nevermind

[slim linden]

a

[sacred junco]

solve over the positive integers : (2020a)^2+(2021b)^2=2022c^2.

[cursive zenith]

I need help with this lol
If a+3/2a-5 then find the sum of all possible integral values of a

Quite hard idk why

[sacred junco]

(a+3)/(2a-5)?

is an integer?

[wise oyster]

@sacred junco nvm that they are being helped in another channel, they mistyped

[sacred junco]

a

[torn escarp]

What are all the integer solutions to $m^ab^b=a^bn^a$?

[sterile pumice]

Merosity

[torn escarp]

with a,b relatively prime and m,n relatively prime

[fervent crest]

Ok the equation is equivalent to $\br{\frac ba}^{\frac ba}=\frac nm$

[sterile pumice]

Whoever

[fervent crest]

Then (b/a)^b is a perfect “a” power

Which implies b^b and a^b are perfect “a” power since a,b are coprime

Which also implies a and b are perfect “a” powers

Also I feel like for any perfect “a” powers a,b, you can find unique coprime n,m satisfying the equation

@torn escarp

[torn escarp]

I suppose similarly we could also run the argument the opposite way too and see (n/m)^a as a perfect "b" power etc etc

I think that would them allow us to do substitutions to get it down to square free relatively prime numbers that would end up having to be equal

[torn escarp]

in particular this forces $a=k^a$ which can only have $a=1$ or $a=-1$ as a solution

[sterile pumice]

Merosity

[torn escarp]

that's nice

[fervent crest]

Wait what?

I don’t follow

[torn escarp]

you said a is a perfect a power

so a=k^a

because these are integers they're pretty restricted

k=a^(1/a) is not an integer for a>1 and is bounded between 1 and 2

then for negative, we have $(-a)^{\frac{1}{-a}} = - \frac{1}{a^{\frac{1}{a}}}$ (when a is odd, undefined otherwise) which is similarly bounded

[sterile pumice]

Merosity

[fervent crest]

Oh true

I need to write it down

Ugh

[torn escarp]

I think I've wrapped it up actually since we can say similar things about m being 1 or -1

$(a,b,m,n)$ solutions are $(-1, \pm 1, m, \mp m)$ and $(1, b, \pm 1, \pm b^b)$

[sterile pumice]

Merosity

[torn escarp]

I believe, I went through and kind of just narrowed it down by the case when a=-1 and then when a=1 yu have m=1 or m=-1

[fervent crest]

Oh i c

[torn escarp]

hmm no I think I found an example that's not in this solution set

(-1,2,4,1) I think would work

writing out as $4^{-1}*2^2 = (-1)^2 * 1^2$ hmm I guess there's a mistake

[sterile pumice]

Merosity

[fervent crest]

So if you rearrange you get $(2/-1)^{2/-1}=4$

[sterile pumice]

Whoever

[fervent crest]

Too lazy for parentheses

And 2 and -1 are perfect -1 powers

[torn escarp]

1/4 close

yeah

[fervent crest]

I meant 4^-1 on the right side

[torn escarp]

I guess maybe that's where the cases are missing, since a negative 'perfect power' is going to be a fraction

maybe it'd be cleaner to break up the cases as $n/m = (b/a)^{b/a}$ when a is positive and negative case as $n/m = (-a/b)^{b/a}$ for a positive here

[sterile pumice]

Merosity

[dusky glacier]

after considering it as mod 4

idk how i would show it to be divisible by 2

i mean a and b would have be something from $\overline{0}, \overline{1}, \overline{2},\overline{3}$

[sterile pumice]

Yes

[haughty lichen]

Try looking at possible values for 3c^2 mod 4 and same for a^2 and b^2 ans their sum

[dusky glacier]

well

a^2 and b^2 are either \overline{0} or \overline{1}

3c^2 is \overline{3} or \overline{0}

so $a \in {0 \pm 4(k_1), \dots} + b\in {0 \pm 4(k_2),\dots} = c \in {0 \pm 4(k),\dots}$

[sterile pumice]

Yes

[dusky glacier]

dont see how the solutions cant be non zero

<@&286206848099549185>

[abstract flax]

@dusky glacier If 3c^2 is 3 and a^2 is 0 or 1 and b^2 is 0 or 1, then there is no possible solution. So 3c^2 must be 0.

[dusky glacier]

but

$3c^2 \text{is} \overline0$

[sterile pumice]

Yes

[abstract flax]

Yes, I'm leaving out overlines, because I'm lazy

[dusky glacier]

and $\overline{0}$ is 0,4,8 and so on tho?

[sterile pumice]

Yes

[abstract flax]

Yes

[dusky glacier]

so its essetially adding 2 multiples of 4 and ending up with a another multiple of 4

[abstract flax]

Yes

[dusky glacier]

so why are the only solutions 0 ?

[abstract flax]

Okay, once you accept the only possibile solutions are multiples of 4. Then take the subset of positive a that are part of a solution. Every subset of positive integers has a least element, so there is a smallest such a. But then dividing through by 4 gives another solution, so then you get an even smaller a. This is a contradiction. So no such a exists.

If there is a positive solution, there must be a smallest one. But every solution gives an even smaller one. So that's a contradiction. So there are no positive solutions.

Oh, it says no nonzero integers, you can repeat the argument above by taking the magnitudes of the solutions.

[dusky glacier]

so

diving by 4 gives solutions that wouldnt be in $\overline0$ ?

[sterile pumice]

Yes

[dusky glacier]

@abstract flax

not sure i understood what you said

[abstract flax]

Suppose there are nonzero integers solutions.

Then there is a solution (a, b, c) of nonzero integers where a has the smallest possible absolute value. So |a| <= |a*| for all other solution (a*, b*, c*) of nonzero integers. Do you follow, yes or no?

[dusky glacier]

no

whats the star

[abstract flax]

That doesn't mean anything

[dusky glacier]

and why are we looking at magnitudes

[abstract flax]

It's just to make it look different to a

[dusky glacier]

ok

[abstract flax]

To get a contradiction

[dusky glacier]

ok, i follow

[abstract flax]

Since (a, b, c) is a solution, we have a^2 + b^2 = 3c^2

[dusky glacier]

ok

[abstract flax]

And since a^2, b^2 and c^2 are multiples of 4, a b and c are multiples of 2.

Yes or no?

[dusky glacier]

yes

[abstract flax]

Then we can divide through by 4 and get (a/2)^2 + (b/2)^2 = 3(c/2)^2

So then (a/2, b/2, c/2) is also a solution of nonzero integers. Yes or no?

[dusky glacier]

yes

[abstract flax]

But |a/2| < |a|

And a is supposed to have the smallest absolute value

So that's a contradiction

[dusky glacier]

i see

[abstract flax]

Yay

[dusky glacier]

ty

[abstract flax]

Np

[sterile pumice]

Sideurk

[sleek cove]

nvm

[sacred junco]

if 3^n divides a for any positive integer n, and a is an positive integer, then a=0?

n can be 1,2,3,4,5,....,n

[light flicker]

yes

[sacred junco]

thanks

[sleek cove]

np

[light flicker]

you're so fucking annoying

[sleek cove]

shut the fuck up weeb

[sacred junco]

Decide whether the number 527 is
a prime number. If the number 527 is a prime
number, then the Little Fermat’s theorem holds for
example for 2. because gcd(2, 527) = 1, we have 2
526 ≡ 1 (mod 527).
using fermats little theorem

[fervent crest]

$2^{526}\equiv1\pmod{527}$ if $527$ is prime

[sterile pumice]

Whoever

[fallow cargo]

Hi I have a question about a line in a proof that confuses me a bit, i wonder if someone can explain it to me in a different perspective

I have this lemma as a tool

and the underlined part is what I'm confused by

[stiff rivet]

if you consider that equation mod 8, there are only 7 possible values you can insert for x

(since every number mod 8 has a representative in 0, 1, 2, ..., 7)

(e.g. 8 is congruent 0 mod 8, 9 is congruent 1 mod 8, ...)

[fallow cargo]

thank you!

I have another question

Give an example of elements showing that the function $\lambda (a+b\sqrt{-5}) = a^2 + 5b^2$ is not a Euclidean function on the integral domain $\mathbb{Z}[\sqrt{-5}]$

[sterile pumice]

jn3008

[fallow cargo]

this is the definition i'm given

i'm not sure how exactly I can prove this

[light flicker]

One way is to use the fact that all Euclidean Domains are Principal Ideal Domains and then show that there's an ideal that's not principal

[fallow cargo]

thanks, but doesn't this not answer the question

i'm trying to show that lambda is not a euclidean function, not Z[sqrt(-5)] is not a euclidean domain right?

and I'm specifically supposed to do it with contradicting examples

[light flicker]

Okay true. I was thinking that if you show that the ring is not a Euclidean domain, then it can't have any Euclidean function, so in particular this Euclidean function doesn't work

[fallow cargo]

i think this question comes up later for me, so this help is definitely useful

but for this specific question

am i supposed to find A, B such that for any Q, R satisfying B = AQ+R, then λ(R) >= λ(A)

i tried expressing these in the form a+b(sqrt(-5)) and it got pretty messy and i made no progress

[fallow cargo]

@light flicker do you think that this is the correct approach for this specific question?

[light flicker]

Yeah I'm not really sure of an easy way to do this, other than to guess values of A and B

I think 3 and 2 +sqrt(-5) might work but don't have paper rn to confirm

[fallow cargo]

ok so I get $2+\sqrt{-5} = 3(\alpha + \beta \sqrt{-5}) + (\gamma + \delta \sqrt{-5})$

[sterile pumice]

jn3008

[fallow cargo]

then $2 = 3\alpha + \gamma$ and $1 = 3\beta + \delta$

[sterile pumice]

jn3008

[fallow cargo]

so $\lambda(3) = 9$ and $\lambda(\gamma+\delta \sqrt{-5}) = 9 -12 \alpha + 9 \alpha ^2 - 30\beta + 45 \beta ^ 2$

[sterile pumice]

jn3008

[fallow cargo]

i'm not sure where to go with this

@light flicker so i need to show that $9\alpha^2 +45 \beta ^ 2 \geq 12 \alpha + 30\beta$ right?

[sterile pumice]

jn3008

[fallow cargo]

so if $\alpha \geq 2$ then $9\alpha^2 \geq 12\alpha$ and if $\beta\geq 1$ then $45\beta^2 \geq 30\beta$ right?

[sterile pumice]

jn3008

[fallow cargo]

so we only need to check the case where alpha is 1

[light flicker]

Well, alpha and beta don't need to be positive integers here

[fallow cargo]

ah i see

but if they are negative then the inequality is trivial right?

i should state this

[light flicker]

Yeah, both individual inequalities are always true when alpha beta are non positive

[fallow cargo]

and so the whole inequality is also true

[light flicker]

yep

[fallow cargo]

then when alpha is 1, the inequality reads $45\beta ^2 \geq 3 + 30\beta$ which is true for any beta and so the proof is complete?

[sterile pumice]

jn3008

[light flicker]

yeah

[fallow cargo]

great, thank you very much

[light flicker]

If you're wondering how I was able to guess those, its because of what I said earlier

The usual way to show that this ring isn't a euclidean domain is to show that the ideal (3, 2 + sqrt(-5)) isn't principal

But there are a lot of other things that work so you probably could've guessed one

[fallow cargo]

i see

[fallow cargo]

can anyone give me a hint for this?

i've started by supposing for a contradiction that $a+b \sqrt{-5} $ cannot be written as a finite product of units and irreducibles and so I have a $a+b \sqrt{-5} = x_2(x_4 (x_6\cdots ))$, where $x_{2m+1} = x_{2m+3} x_{2m+4} $ and so we obtain a sequence $x_1, x_3, x_5, \cdots$ that aren't units nor irreducibles. Where do I go from here?

[sterile pumice]

jn3008

[fallow cargo]

please tag me if you reply ❤️

[grave carbon]

Okay, so I’m trying to prove this by FT Arithmetic, and I’m not sure where to go next. I need help

[sterile pumice]

beeswax

[leaden swan]

If k wasn't a perfect square,you can write a^2k as m^2c where c is square free(prime power is 1 for all primes present in c and atleast one prime divides c)

A perfect square cannot written in that form because all prime powers are even

[grave carbon]

So, from that, k must be a perfect square?

[leaden swan]

Yes

It's basically a parity check

[grave carbon]

Okay, I understand.

@leaden swan Wait, if I went about it how I have it in the screenshot, how would I continue it to argue that way?

[leaden swan]

If t wasn't a square some prime power is odd

The power of that prime in a^2t is odd

So a^2t cannot be a square

So t has to be a square,since we know a^2 t is a square

[grave carbon]

Okay, I’m having some trouble with this. Last week, I proved this without FT Arithmetic, but now that I need to use the theorem, I’m not sure how I would use it

<@&286206848099549185>

[silver solar]

It would help to write all numbers involved into their (unique) prime factorizations

[grave carbon]

@silver solar Is this the right direction?

[silver solar]

Looks like it

[grave carbon]

I'm not quite sure how I would get to the point $ab|cd$. I have
$$cd=as(\text{prime factorization of d})$$
$$cd=bt(\text{prime factorization of d}).$$
If I multiply together $$cd(cd) = abts(\text{prime factorization of d})^2$$

[sterile pumice]

beeswax

[silver solar]

Hmm

How about this: since $a|b$, we have that $\alpha_i\le\beta_i$

[sterile pumice]

(R/I)/(J/I) shark PhD

[grave carbon]

Right

[silver solar]

And $b|c$ implies $\beta_i\le\gamma_i$

[sterile pumice]

(R/I)/(J/I) shark PhD

[silver solar]

So in particular $\alpha_i+\beta_i\le\alpha_i+\gamma_i$

[sterile pumice]

(R/I)/(J/I) shark PhD

[silver solar]

But also, since $\alpha_i\le\beta_i$, we have that $\min(\alpha_i,\beta_i)=\alpha_i$

[sterile pumice]

(R/I)/(J/I) shark PhD

[silver solar]

So in fact $\alpha_i+\beta_i\le\min(\alpha_i,\beta_i)+\gamma_i$

[sterile pumice]

(R/I)/(J/I) shark PhD

[grave carbon]

I see

[silver solar]

This is basically the answer

LHS of the inequality are the prime powers of ab
RHS are the prime powers of cd

[topaz wagon]

I think you could prove this by induction, using the norm N(a+b\sqrt{5}) = a^2 + 5b^2. In terms of thinking about the problem intuitively, you might notice that is sounds a lot like the fundamental theorem of arithmetic. You'd prove the fundamental theorem of arithmetic by strong induction on the natural numbers, and you can do something similar here by induction on the value of the norm.

[silk vine]

If you consider S¹(Q) the set of rational points in S¹, then we know that given one known rational point of S¹, we can find all of them by simply considering a known rational point of S¹, say (p,q), then we can find all the other rational points on S¹ by simply considering all the lines with rational slope that pass through (p,q) and intersect S¹.

So in some sense S^1(Q) is finitely generated by a single rational point.

Now

We know that for an elliptic curve E, the Mordell-Weil group E(Q) of rational points of E is finitely generated.

And the thing is

I want to write a little bit a bout the mordell-weil theorem for a final project on a number theory class that I am taking

and I would like to give an example of trying to find rational points on an elliptic curve E

And I would like to ask if some of you guys know a cool example of an elliptic curve whose rational points are easy to find

and whose way to find them has somewhat of a geometric intuition behind, such as finding the rational points of S^1

I hope this question is not that bad formulated

I just want to give a nice little example of computing E(Q) explicitly

and that has somewhat of a geometric intuition behind

[light flicker]

I mean, if you find an elliptic curve of rank 1 with no torsion, then taking a generator and adding it to itself (and doing the same for the inverse) will give you all the rational points. For example https://www.lmfdb.org/EllipticCurve/Q/37a/

[silk vine]

Oh

Didn't know that page

There's tons of examples of elliptic curves

nice

[light flicker]

I'll think about it later, but you can probably come up with such an example with a simple rational point

[silk vine]

Ok, thanks

Hit me up when you think of a nice example

[torn escarp]

I think finding a generator is difficult in general like finding a prime number, but maybe there are particular curves where finding a generator is simple. Once you have that though, like he said, elliptic curve addition is very geometric. You can imagine drawing a line through two points (or a tangent line through a single point if adding a point to itself) then the "sum" is the reflection of the point where the line intersects across the x-axis. If you don't know about this, you should learn about elliptic curve addition

[silk vine]

Yeah, I know it, my question was not really related to the group law on a elliptic curve, but that's ok.

I just would like an example of an elliptic whose group E(Q) is fairly easy to compute.

It would be interesting if somewhat this computation relied on a certain geometric intuition, say.

But I guess that giving an example of computation of E(Q) even if the computation is not that insightful would be fair enough.

[light flicker]

Yeah I'm not sure there's much geometric intuition for finding a generator, or showing that the rank has to be 1 or showing that the torsion is trivial (beyond the order 2 elements). But once you show those things, then the elliptic curve addition is geometric

[light flicker]

@silk vine Yeah so I think the simplest example is the curve y^2 + y = x^3 - x which has rank 1 and torsion 0 and has (0,-1) as a generator

[silk vine]

I'll try to prove these results

thanks

[light flicker]

This is the example I linked earlier too

I didn't prove any of these either, I just believe what Sage tells me

[obsidian slate]

Im working on a problem that basically boils down to

[light flicker]

the max of what?

How did you prove the 46 part? I don't think its true?

You can split the 17 points into a group of 8 and a group of 9, and then just form the complete bipartite graph between them, e.g. draw every edge between the two different groups. This doesn't have a triangle but has 72 edges.

@obsidian slate

https://en.wikipedia.org/wiki/Turán's_theorem

Yeah I don't think this is enough. This is a Ramsey theory type problem, https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers is something you might want to look at

And then look at Ramsey's theorem itself

[light flicker]

yeah that sounds right

[tidal canopy]

Can anyone explain how to show this is false?

I have tried this but am not sure how to get a contradiction

[light flicker]

To show something like this is false, you need to just show a counterexample to the statement right

[tidal canopy]

Yea

I tried the proof thing just for practice, though, to see if i could understand it better

[light flicker]

So just try it out for small n and see if you can get a counterexample

True, sometimes trying to prove the false statement can help you see where you could find a counterexample

[tidal canopy]

Okay, think I was able to find a counter example

so that's pretty straightforward

[light flicker]

What was it?

[tidal canopy]

a=2, b=5, n=21

[light flicker]

Can you explain how this is a counterexample?

[tidal canopy]

2^2 = 5^2 (mod 21) or 4 = 25 (mod 21)

But, 2 != 5 (mod 21)

and, 2 != -5 (mod 21)

[light flicker]

Right that works

Even easier is to see that 2^2 = 0^2 (mod 4)

[tidal canopy]

Right right

okay, that definitely helps

[light flicker]

This statement is also true when n is prime, which is something you might've seen if you tried to prove it

[tidal canopy]

Yeah, I see

Because then you can show that it must be the case that n | (a+b) because of Euclid's Lemma?

[light flicker]

It must be the case that either n | (a + b) or n | (a - b) by Euclid's lemma yes