Finding Natural Numbers n Satisfying a Congruence

In summary, the conversation discusses finding natural numbers n that satisfy the equation n\sigma (n) \equiv 2(mod\varphi(n)), with a focus on finding non-prime numbers that fit the criteria. The conversation notes that under one million, only 1,4,6, and 22 comply, with 4 and 6 being exceptions. The proof for this is condensed into three sets of possibilities: n=p, n=2p, and n=4p, with p being a prime >2. The conversation concludes that n=p always complies, n=4p does not comply, and n=2p complies only if n sigma(n) = 6p^2+6p ==
  • #1
hadi amiri 4
98
1
fin all natural numbers n that [tex]n\sigma (n) \equiv 2(mod\varphi(n)) [/tex]
 
Physics news on Phys.org
  • #2
This is true for all primes, since n(n+1)-2 = (n+2)(n-1). The interesting part is, which non-primes are also in the list.

Edit: under one million, only 1,4,6,22 comply. Hmmm.
 
Last edited:
  • #3
4 and 6 do not comply:

4: n sigma(n) = 4*7 = 28, phi = 2
6: n sigma(n) = 6*12 = 72, phi = 2
 
Last edited:
  • #4
I understood the condition as "both n . sigma(n) and 2 having the same residue modulo phi(n)", and not as "the residue of n . sigma(n) modulo phi(n) is 2".
 
  • #5
Good point.

Either way, no other solutions for n up to 10^8.
 
  • #6
Okay, here's the condensed proof.

First we need a lemma. If a == b (mod c) and b!=0, then |b| >= gcd(a,c). Specifically, if a == 2 (mod c), then a and c have no common factors greater than 2.

Factorize n and plug in the expressions for phi and sigma in terms of prime factors into the equation.

If any prime p>2 is present in the factorization more than once, LHS is a multiple of p and RHS is a multiple of p: no solution.

If there's more than one prime p>2 in the factorization, or if n is a multiple of 8, LHS is a multiple of 4 and RHS is a multiple of 4: no solution.

That leaves us with three sets of possibilities, n=p, n=2p, n=4p, where p is a prime >2, and a fourth possibility n=4.

n=p always comply.

n=4p don't comply because LHS and RHS are multiples of 4.

n=2p comply iff n sigma(n) = 6p^2+6p == 2 (mod p-1)

which is the same as 10 == 0 (mod p-1) which is true for p=2, p=3 and p=11, yielding solutions n=4, n=6, n=22.
 
Last edited:

1. What are natural numbers?

Natural numbers are whole numbers greater than zero, including 1, 2, 3, and so on.

2. What does it mean for a number to satisfy a congruence?

A number satisfies a congruence if it leaves the same remainder when divided by a given number, known as the modulus.

3. How do you find natural numbers that satisfy a congruence?

To find natural numbers that satisfy a congruence, you can use the modulo operation. Take the modulus of the given number and the desired remainder to find the smallest natural number that satisfies the congruence. Then add multiples of the modulus to this number to find other solutions.

4. Can any natural number satisfy a congruence?

Not all natural numbers will satisfy a congruence. It depends on the modulus and the desired remainder. There may be no solutions, one solution, or multiple solutions.

5. Why is finding natural numbers that satisfy a congruence important?

Finding natural numbers that satisfy a congruence is important in many areas of mathematics, such as number theory and cryptography. It also has practical applications in computer science, such as in generating random numbers.

Similar threads

  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
351
  • Linear and Abstract Algebra
Replies
2
Views
842
  • General Math
Replies
3
Views
992
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
855
  • Precalculus Mathematics Homework Help
Replies
1
Views
666
  • Precalculus Mathematics Homework Help
Replies
2
Views
654
  • Precalculus Mathematics Homework Help
Replies
2
Views
946
Back
Top