Are My Congruence Calculations Correct?

  • Context: Undergrad 
  • Thread starter Thread starter 1+1=1
  • Start date Start date
  • Tags Tags
    Brain
Click For Summary

Discussion Overview

The discussion revolves around the correctness of congruence calculations involving modular arithmetic, specifically whether \( a^{13} \equiv a \mod 2730 \) and \( a^{7} \equiv a \mod 63 \) under certain conditions on \( a \). Participants explore the application of Fermat's Little Theorem and other number theory concepts to validate these congruences.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants suggest using Fermat's Little Theorem to establish that \( a^{13} \equiv a \mod 13 \) and inquire if this can be extended to \( \mod 2730 \).
  • Others argue that additional proof is necessary to show \( a^{13} \equiv a \mod 2730 \) since it requires consideration of multiple prime factors.
  • One participant proposes that if \( a \) is divisible by 9, then \( a^{7} \equiv a \mod 63 \) can be shown by demonstrating \( a^{7} \equiv a \mod 7 \) and using properties of divisibility.
  • Concerns are raised about the validity of dividing congruences, particularly in cases where \( a \) may equal zero or other specific values.
  • Some participants express uncertainty about the sufficiency of showing congruences for individual prime factors to conclude congruences for their product.
  • There are discussions about the reflexive property of congruence and its implications in specific modular cases.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the sufficiency of the proofs presented. There are competing views on the application of Fermat's Little Theorem and the conditions under which the congruences hold.

Contextual Notes

Some arguments lack rigor, particularly regarding exceptions in modular arithmetic. The discussion highlights the need for careful consideration of conditions under which congruences are valid, especially when involving zero or specific divisors.

1+1=1
Messages
93
Reaction score
0
show that a^13 is congruent to a (modulo 2730)

if a is an integer such that a is not divisidble by 3, or such that a IS divisible by 9, then a^7 is congruent to a (mod 63)

with these, could i just divide the mod numbers by the powers? that is what i am doing, but it seems like as though it ISN'T right... anyone help ?
 
Physics news on Phys.org
Have you come across Fermat's Little Theorem ?

a^p == a (mod p) for prime p
 
gokul, could i say that b/c of fermat's thm, i can say that it IS == to a, because of the fact that 13 is prime? would i need to prove any further? also, could that work for the second one? anyone else think so?
 
What exactly are you asking? According to that theorem

a^13 = a (mod 13), but you need to show a^13 = a (mod 2730), so of course you need to prove more! I've never taken any courses on number theory, but you might know a theorem that takes advantage of the fact that 2730 = 0 (mod 13).
 
ok so i could set it up, then say, "according to fermat's theorem,... and apply the theorem to this probloem?
 
Uhh.. are you asking if you're allowed to use Fermat's Little Theorem? I suppose you should ask your teacher/prof/t.a.
 
I haven't taken any courses either...but this is what I would do. The folks that really know some number theory probably have a far better approach.

2730 = 13*7*5*3*2
So we are done if we can show that a^13 == a (mod n), for n=2,3,5,7, and 13.
Use both forms of the Little Theorem...
a^p == a (mod p), for all prime p and a^(p-1) == 1 (mod p) for prime p, when p does not divide a.

Clearly a^13 == a (mod 13) ---- (1)

Also a^7 == a (mod 7) and
a^6 == 1 (mod 7), so
(a^7)*(a^6) = a^13 == a*1 (mod 7) ---(2)

Again, a^5 == a (mod 5)
and a^4 == 1 (mod 5) => a^8 == 1 (mod 5)
Hence a^13 == a (mod 5) ---(3)

Likewise, show this for n=3 and n=2..and you are done.

This proof lacks some rigor (in that, for each result, the exceptions need to be covered. This is not hard at all), but I'm going to leave that to you to find and fill in.
 
Last edited:
Gokul43201

I don't know why it's sufficient to show that [itex]a^{13} \equiv a\ (\mbox{mod }n)[/itex] for those n, but unless a = 1 or a = 0, a cannot be congruent to a (mod 2).

1+1=1

For your second question, part of it is easy:

To prove [itex]a^7 \equiv a\ (\mbox{mod }63)[/itex] if a is divisible by 9, we can start by saying:

[tex]a^7 \equiv a\ (\mbox{mod }7)[/tex]

Therefore, for some integer x:

[tex]a^7 = 7x + a[/tex]

Now, since a is a multiple of 9, [itex]a^7[/itex] must also be a multiple of 9, and thus 7x must also be a multiple of 9. So, for some integer y, x = 9y. Now, we have:

[tex]a^7 = 63y + a[/tex]

I think this is sufficient to prove [itex]a^7 \equiv a\ (\mbox{mod }63)[/itex] if a is divisible by 9.
 
Last edited:
No dividing by 0

Much of the work on the problem is good, but remember that we can not divide by 0. For that reason forget about a^p ==a implies a^(p-1) ==1. That is not true in general. For example in the case of a^13 = =a Mod 7, we have a^13 =a^7 x a^6 ==a x a^6 == a^7 ==a Mod 7, this is true even for a=7. The arithmetic is 7^7 ==7==0 Mod 7, but 7^6 ==0 Mod7 also, not 1.
 
Last edited:
  • #10
If a==b (mod n) and a==b (mod m), then a==b (mod mn), if gcd(m,n)=1.

AND

If n divides a, ie. if a==0 (mod n), then clearly a^k == 0 (mod n), which implies that a^k==a (mod n).

I think I've said too much already.
 
Last edited:
  • #11
robert Ihnot said:
Much of the work on the problem is good, but remember that we can not divide by 0. For that reason forget about a^p ==a implies a^(p-1) ==1. That is not true in general. For example in the case of a^13 = =a Mod 7, we have a^13 =a^7 x a^6 ==a x a^6 == a^7 ==a Mod 7, this is true even for a=7. The arithmetic is 7^7 ==7==0 Mod 7, but 7^6 ==0 Mod7 also, not 1.

I'm not sure if this is directed at me...

I insist that nothing I have said is wrong, and that I do not carelessly divide congruence relations. Please re-read what I have written.
 
  • #12
AKG said:
Gokul43201

I don't know why it's sufficient to show that [itex]a^{13} \equiv a\ (\mbox{mod }n)[/itex] for those n,
Post#10, line 1.

but unless a = 1 or a = 0, a cannot be congruent to a (mod 2).

What ? Any number is always congruent to itself ! Isn't 'congruence' a reflexive relation ? Isn't 0 divisible by all numbers ?

1+1=1

For your second question, part of it is easy:

To prove [itex]a^7 \equiv a\ (\mbox{mod }63)[/itex] if a is divisible by 9, we can start by saying:

[tex]a^7 \equiv a\ (\mbox{mod }7)[/tex]

Therefore, for some integer x:

[tex]a^7 = 7x + a[/tex]

Now, since a is a multiple of 9, [itex]a^7[/itex] must also be a multiple of 9, and thus 7x must also be a multiple of 9. So, for some integer y, x = 9y. Now, we have:

[tex]a^7 = 63y + a[/tex]

I think this is sufficient to prove [itex]a^7 \equiv a\ (\mbox{mod }63)[/itex] if a is divisible by 9.

This looks okay. But there's a shorter way...see post#10.
 
Last edited:
  • #13
Much of the work on the problem is good, but remember that we can not divide by 0. For that reason forget about a^p ==a implies a^(p-1) ==1. That is not true in general.

No, it's not true in general, but it IS true when p is prime and p doesn't divide a (i.e a != 0 (mod p)). Besides, Gokul43201 was talking about modulo p, so your counterexample doesn't hold.
 
Last edited:
  • #14
first of all, thank you to all who helped with the input! i too figured some of it out on my own, but with this it reinforced what i had! isn't that what learning is about, doing some on your own then seeing what others have? i wish i could meet you all and thank yall in person! :biggrin:
 
  • #15
Gokul43201 said:
What ? Any number is always congruent to itself ! Isn't 'congruence' a reflexive relation ? Isn't 0 divisible by all numbers ?
Oh, you're right. I was thinking that a (mod 2) didn't work if a > 2, I thought 17 (mod 4) would be wrong, and 1 (mod 4) would be the right way to do it, but I suppose they're both right, I've just never seen "17 (mod 4)" or "a (mod 2)" [for a > 2] before.
 
  • #16
I thought you said, I took it from what you wrote:

Gokul43201 said:
I'm not sure if this is directed at me...

I insist that nothing I have said is wrong, and that I do not carelessly divide congruence relations. Please re-read what I have written.
This what you wrote:
Also a^7 == a (mod 7) and
a^6 == 1 (mod 7), so
(a^7)*(a^6) = a^13 == a*1 (mod 7) ---(2)
 
  • #17
the fact of the problem

Gokul43201 said:
I'm not sure if this is directed at me...

I insist that nothing I have said is wrong, and that I do not carelessly divide congruence relations. Please re-read what I have written.

You said, Also a^7 == a (mod 7) and
a^6 == 1 (mod 7), so
(a^7)*(a^6) = a^13 == a*1 (mod 7) ---(2)

Here we really want X^13 ==X Mod 2730, so I thought from how I read you that you were not considering X =7,14,21...etc. That is how I thought about it.
 

Similar threads

  • · Replies 5 ·
Replies
5
Views
3K
Replies
4
Views
3K
  • · Replies 2 ·
Replies
2
Views
6K
  • · Replies 8 ·
Replies
8
Views
11K
  • · Replies 3 ·
Replies
3
Views
5K
  • · Replies 3 ·
Replies
3
Views
5K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 2 ·
Replies
2
Views
3K
Replies
1
Views
3K
  • · Replies 3 ·
Replies
3
Views
4K