blackpenredpen

math for fun 

  1. Discussions
  2. Math Problems
  3. Is this always true or not ? And if it is, how to prove it.
Search
Jotadiolyne Dicci
Mar 28, 2020
  ·  Edited: Mar 29, 2020

Is this always true or not ? And if it is, how to prove it.

Hello everyone, I have a question. During a congruence calculation, I found a very strange pattern.

Let a,t be integers and d the largest factor of t having a power greater than or equal to 2,

If a^2 = 0 (mod t) then a = 0 (mod t/d)


For example :

a^2 = 0 (mod 8) a^2 = 0 (mod 16)

8 = 2^3 Here 2 is the largest factor 16 = 2^4 = 4^2 Here 4 is the largest factor

a = 0 (mod 8/2) = 0 (mod 4) a = 0 (mod 16/4) = 0 (mod 4)


Is that true? And if it is, how can we prove it?

Honestly, I really don't know what to make of that.

0
Eric Steckx
Mar 29, 2020

Think in term of divisibility!

Let t=k.d² so no square remains in k (as d is the larger factor having a power ≥ 2)

a²≡0 (mod t) means that t ∣ a² => k.d² ∣ a²

As there is no square in k, then k.d ∣ a and, as k.d=t/d, t/d ∣ a

In other words a≡0 (mod t/d) QED


Is all this clear ?

Jotadiolyne Dicci
Mar 29, 2020

Wow! Thank you very much, I hadn't thought of that!

There's just one thing I don't quite understand. Why is it that when there's no square in k, we can say directly that k.d divides a ?

0
Eric Steckx
Mar 29, 2020

@Jotadiolyne Dicci

If there is no square in k, all prime factors of k have a power of one, so if they are factors of a², they all must be factors of a, then k ∣ a.

If d² ∣ a², it seems obvious that d ∣ a.

CASE 1 : If it is no common prime factor between k and d : k ∣ a and d ∣ a => k.d ∣ a

CASE 2 : ∃ p (prime) so that p ∣ d and p ∣ k <=> p³ ∣ t. Then we must have t ∣ a² => p⁴ ∣ a², as all prime factors of a square must have an even power. The remainding not common factors between k and d can be treated as in case 1.


I don't know if this explanation is clear, but try with an example of both case, and you see quickly what I mean.

Jotadiolyne Dicci
Mar 29, 2020

@Eric Steckx Thank you very much! I understand better now!

0