Congruences of (x^n-2) and its factors

  • Context: Graduate 
  • Thread starter Thread starter AntonVrba
  • Start date Start date
  • Tags Tags
    Factors
Click For Summary

Discussion Overview

The discussion revolves around the congruences of the expression (x^n - 2) and its factors, particularly focusing on the behavior of these factors under modulo 8. The scope includes mathematical reasoning and exploration of properties related to odd integers and even powers.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • Anton asserts that for all odd x, (x^n - 2) is congruent to 7 modulo 8 and questions why its factors are either congruent to 1 or 7 modulo 8.
  • One participant challenges Anton's assertion by providing a counterexample with x = 3 and n = 3, leading to a result that appears to contradict the claim.
  • Anton later clarifies that n is even, which shifts the context of the discussion.
  • Another participant emphasizes that all odd squares are congruent to 1 modulo 8, suggesting this is a key point in the discussion.
  • A participant notes that the original question implies that x^n - 2 is trivially -1 modulo 8 and proposes that proving all factors are either plus or minus 1 modulo 8 is complex.
  • One participant suggests considering quadratic residues as a potential approach to the problem.
  • Another participant discusses specific cases of odd integers and their squares, indicating that subtracting 2 results in a congruence of -1 modulo 8.
  • There is mention of examining the factors of specific examples, such as 11^2 - 2 = 119, which yields factors congruent to 1 or 7 modulo 8.
  • A later reply introduces quadratic reciprocity as a method to find solutions to x^2 = 2 modulo p, referencing external material for further exploration.

Areas of Agreement / Disagreement

Participants express differing views on the validity of Anton's initial assertion, with some providing counterexamples and others supporting the idea that the factors of x^n - 2 may indeed be constrained to certain congruences. The discussion remains unresolved with multiple competing perspectives.

Contextual Notes

There are limitations regarding the assumptions made about the values of x and n, particularly the distinction between odd and even integers. The discussion also reflects uncertainty in the algebraic manipulations and the implications of quadratic residues.

AntonVrba
Messages
92
Reaction score
0
It is easy to show that for all odd x that:
(x^n-2) = 7 (mod 8)

but why are the factors of above either congruent 1 or 7 modula 8, i.e
factor(x^n-2) = {1,7} (mod 8)

can anyone give me a hint.

regards
Anton
 
Physics news on Phys.org
If x = 3 and n = 3 then [itex]x^n - 2 = 25 = 5^2[/itex] so your assertion appears to be false.
 
Oops sorry - I forgot to add n is even
 
WHERE DID THE N COME FROM? The simple fact is that all odd squares ae congruent to 1 Mod 8.
 
The question is asking for more than that, it even starts by observing that x^n-2 is trivally -1 mod 8. it then asks you to show that all factors of x^n-2 are then either plus or minus 1 mod 8 which is a little bit trivcky, I think.

My inital reaction is that this seems as though it might be false, small counter examples seem to satisfy the proposition, so my initial reaction might be wrong.

if indeed it is true, then my first observation is it suffices to prove this for n=2 and all odd x: if the conjecture is true, this is a special case of it, and if it is true for n=2 then one can deduce the conjecture by noting that x^{2m}=(x^m)^2

however, even then nothing obvious springs to mind

x^2-2 = (x-1)(x+1) - 1 but i don't see that it reall helps.

perhaps some reduction argument helps, or am i missing something obvious?
 
Big hint: think quadratic residues.
 
I must be missing something. Since he is talking about odd squares, X^n-2, X is odd, n is even, we know that all odd squares are congruent to 1 Mod 8. So that if we subtract 2 it is congruent to -1==7 Mod 8.

If the algebra is a problem, all you have to do is look at the cases of X==1,3,5,7. This is four cases.

By induction if X^2 ==1 Mod 8, we look at (X+2)^2 ==X^2+4X+4 ==1+4(X+1), since (X+1) is even 4(X+1) ==0 Mod 8.
 
It's a question about the factors of x^n-2. e.g. 11^2-2=119. Then the factors of 119 are 1, 7, 17 and 119, all are congruent to 1 or 7 mod 8.
 
robert Ihnot said:
I must be missing something.


It's not the number, but its factors.
 

Similar threads

Undergrad Congruence for Symmetric and non-Symmetric Matrices for Quadratic Form
  • · Replies 7 ·
Replies
7
Views
2K
Graduate When n*(n+1)/2 - k is never a square
  • · Replies 2 ·
Replies
2
Views
2K
Graduate What Are the Surrogate Number Congruences for Moduli Other Than Its Factors?
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Looking for a creative or quick method for finding roots in GF(p^n)
  • · Replies 3 ·
Replies
3
Views
2K
Graduate How can I find a x such that the order of 2 mod x is n?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Factorization & Congruence to 4: Proven or Researched?
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Prove Even # Transpositions in Identity Permutation w/ Induction & Contradiction
  • · Replies 8 ·
Replies
8
Views
5K
Undergrad Can Solving n = x (mod 10x+1) Simplify Factoring Numbers?
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Are there any primes of the form 10^k + 1 above 101?
  • · Replies 21 ·
Replies
21
Views
22K
Graduate Number of quadratic residues mod N>1
  • · Replies 3 ·
Replies
3
Views
4K