Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

4
votes
2answers
58 views

positive Integer value of $n$ for which $2005$ divides $n^2+n+1$

How Can I calculate positive Integer value of $n$ for which $2005$ divides $n^2+n+1$ My try:: $2005 = 5 \times 401$ means $n^2+n+1$ must be a multiple of $5$ or multiple of $401$ because ...
0
votes
1answer
154 views

Legendre symbol proof

Show that if $a$ is a quadratic residue of the odd prime $p$, then the solutions of $x^2\equiv{a}\pmod {p}$ are $x\equiv{\pm a^{n+1}}\pmod {p}$ if $p=4n+3$. Proof Assume $p=4n+3$ and ...
1
vote
1answer
69 views

What model do you get from PA without addition and multiplication?

I have the feeling that this question is trivial, but I cannot figure the answer by myself nor from the stuff I have read. So the question is if addition (and multiplication) can be shown as a theorem ...
0
votes
3answers
207 views

Can countability coexist with infinity?

This question concerns the countability of the real numbers. First I will show how I count the numbers between 0 and 1 on the real line. It is done by reversing digits behind the coma, so that e.g. ...
3
votes
2answers
71 views

Number of Solutions for Congruency Equations

I'm leaning congruency equations, so for example: $$ ax \equiv b \pmod m $$ I have that the number of solutions will be equal to $d$, where $$ d = \gcd(a, m). $$ And the solutions ae: $$ ...
2
votes
1answer
115 views

A trigonometric identity for special angles

Prove that for a natural number $n$, $$\prod_{k=1}^n \tan\left(\frac{k\pi}{2n+1}\right) = 2^n \prod_{k=1}^n \sin\left(\frac{k\pi}{2n+1}\right)=\sqrt{2n+1}.$$
3
votes
1answer
130 views

On Sixth Powers $x_1^6+x_2^6+\dots+x_6^6 = z^6$

Fourteen years ago, in 1999 (has it been that long?) Merignac started a search for, $$x_1^6+x_2^6+\dots+x_6^6 = z^6$$ using the five congruence classes, $$\begin{aligned} ...
1
vote
1answer
282 views

Determining whether a quadratic congruence is solvable using Legendre symbol

I'm trying to detect whether the quadratic congruence $2x^2 + 5x - 9$ is congruent to $0$ modulo $101$. I've think I'll be able to detect whether there is or there is no solution using Legendre ...
0
votes
2answers
102 views

Odditiy: An Analysis of Skew-Symmetric $n\times n$ Matrices

Let $A \in M_{n×n}(\mathbb{R})$ be a skew-symmetric matrix, i.e., $A^t = −A$. Prove that if $n$ is odd, then $\det{A} = 0$.
2
votes
2answers
139 views

Proving two equations involving the greatest common divisor

Show or prove that $$\gcd \left(\frac{a^{2m}-1}{a+1} ,a + 1\right )=\gcd(a + 1 , 2m),$$ and that $$\gcd \left(\frac{a^{2m + 1}+1}{a+1} , a + 1\right)=\gcd(a + 1 , 2m + 1).$$
2
votes
1answer
42 views

Cyclic shifts when multiplied by $2$.

I was trying to solve the following problem: Find a number in base $10$, which when multiplied by $2$, results in a number which is a cyclic shift of the original number, such that the last digit ...
1
vote
1answer
334 views

Modulus Cancellation Law

I'm trying to understand the proof for cancellation law in modulus which states that: ...
3
votes
1answer
125 views

Why is $n=\frac{2p^2+2pq+2pr+q^2+2qr+r^2}{p+q+r}$, where $n$ is $\text{prime}$, of form such that $p\pm a,p\pm b,$ are $ \text{prime}, 1<a<b<n$

Why is $n= \left\lfloor \frac{2p^2+2pq+2pr+q^2+2qr+r^2}{p+q+r} \right\rfloor$, where $n$ is $\text{prime}$, of form such that $p\pm a,p\pm b,$ are $ \text{prime}, 1<a<b<n$? Consider this: ...
1
vote
1answer
50 views

Lengendre symbol calculation

I'm trying to calculate the lengendre symbol of (3/383) without using the Quadratic Reciprocity Law, and with not much success. I've thought about checking if 2^191 is congroent to 1 modulo 383 but it ...
5
votes
4answers
316 views

Prove or disprove statements about the greatest common divisor

Help with prove or disproving either of these statements would be really appreciated, one or the other is fine, I just need a start or a solution to one and I'm sure I could probably figure the other ...
19
votes
1answer
353 views

To prove that $2^{3n}+2^n +1$ is not a perfect square.

Question: Prove that $2^{3n} + 2^n + 1$ cannot be a perfect square for any natural $n$. I attempted this question and failed in two different ways. 1) I considered a polynomial $p(x) = x^3+ x + 1 - ...
0
votes
1answer
59 views

Why is $\{n=4r+1,r = {n-1\over 2}\}\subset \mathbb{P}$ true under these conditions?

Let $p=p_k$, $q=p_{k+1}$ and $r=p_{k+2}$, where $p_m$ denotes the $m$th prime. I conjecture that whenever $n$ is prime, where $n$ is defined as follows: $$n = 1+\left(\left\lfloor{p\over ...
3
votes
3answers
190 views

Finding inverse modulo

I'm trying to find "the smallest positive multiple of 100" that leaves remainder 9 when divided by 19. Here is what I have done before I got stuck: $x ≡ 9 \mod 19$ $\gcd(9,19) = \gcd(19,9)\\ ...
2
votes
1answer
56 views

Representations of Primitive roots

Start by letting $p$ be an odd prime and let $\Pi_{i=1}^{k}$ $q_{i}^{\alpha_i}$ be the canonical factorization of $p-1$. The goal is to show that every primitive root $g$ (mod $p$) has a ...
2
votes
4answers
340 views

How to find the number of positive devisors of $50,000$

How to find the number of positive devisors of $50,000$, I would like to know that what mathematical formulae I need to use here as it is a big number to calculate mentally, I am sorry to ask if this ...
1
vote
2answers
162 views

Proving x and y is divisible by p (prime).

If p is a prime number and x and y are integers, how do I prove "if xy and x+y are both divisible by p, then x and y is divisible by p"? I started like this.. 1) p divides xy, so p divides x or p ...
9
votes
4answers
342 views

Should $\mathbb{N}$ contain $0$? [closed]

This is a classical question, that has led to many a heated argument: Should the symbol $\mathbb{N}$ stand for $0,1,2,3,\dots$ or $1,2,3,\dots$? It is immediately obvious that the question is ...
3
votes
2answers
76 views

How to show: if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$? [duplicate]

A little stumped on this problem, any help would be greatly appreciated. Show that for all $a,b,c \in \mathbb{Z}$, if $b \mid a$ and $c \mid a$ and $\mathrm{gcd}(b,c) = 1$, then $bc \mid a$.
0
votes
1answer
25 views

Counting couples of numbers

I have no trouble believing that, if $|n| \leq J$, then $$\#\{ (j_1,j_2) \in \{ 1,...,J \} \, | \, j_1-j_2 = n \} = J-|n|,$$ but can anyone explain it a little more formally? Thank you in advance ...
3
votes
0answers
252 views

primes of the form $p=8k+1, 8k+3$ can be expressed as $p=a^2+2b^2$

I have trouble showing that primes of the form $p=8k+1, 8k+3$ can be expressed as $p=a^2+2b^2$. Thanks in advance.
0
votes
2answers
154 views

Prove that the number of solutions to $x^a = 1 \pmod p$ in $\mathbb Z_p^\times$ is $\gcd(a,p-1)$ [closed]

Let $p$ be a prime number and $a\geq 1$ an integer. Show that the number of solutions to $x^a = 1 \pmod p$ in $\mathbb Z_p^\times$ is $\gcd(a,p-1)$.
1
vote
1answer
76 views

Revised: Primes of form $p \equiv m \in S \mod x \ $

Refer to this question for background. I was speculating if there was an elegant way to define sequences A007645,A002313,A045357,A045407,A042986,A045331, A045425,A045374,A045400,A045350,A042988; ...
6
votes
1answer
114 views

If an integer $n$ is such that $7n$ is the form $a^2 + 3b^2$, prove that $n$ is also of that form.

If an integer $n$ is such that $7n$ is the form $a^2 + 3b^2$, prove that $n$ is also of that form. I thought that looking at quad residues mod $7$ might??? help. But that didn't take me anywhere so ...
5
votes
2answers
191 views

Find the greatest integer $k$ for which $1991^k$ divides $1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$

Find the greatest integer $k$ for which $1991^k$ divides $$1990^{{1991}^{1992}}+1992^{{1991}^{1990}}$$ It is easy to see that $k \geq 1$ as $1990 \equiv -1$ and $1992 \equiv 1 \pmod{1991}$ Also, I ...
8
votes
3answers
3k views

Infinitely many primes of the form $4n+3$

I've found at least 3 other posts$^*$ regarding this theorem, but the posts don't address the issues that I have. Below is a proof that for infinitely many primes of the form $4n+3$, there's a few ...
2
votes
1answer
124 views

Number array divided into several parts, genelize $a>b>c>d>0$ so $ab+cd>ac+bd$ to more numbers

Now, we have an original number array: $$a_1 > a_2 > a_3 > ... > a_{mn} > 0$$, I wonder whether the following inequality is the truth, if so, could you give me the proof or some ...
2
votes
1answer
60 views

Prove that $n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}$.

Let $c \not= 1$ be a real positive number, and let $n$ be a positive integer. Prove that $$n^2 \leq \frac{c^n+c^{-n}-2}{c+c^{-1}-2}.$$ My initial thought was to try and induct on $n$, but the ...
1
vote
1answer
87 views

Regarding definition of cuban primes

While considering the relationship between $6n-1$ (OEIS A002476) and generalized cuban primes(OEIS A007645) I came across something I thought was interesting: Seems like the description of ...
0
votes
1answer
80 views

Generating primes from other primes

For a natural number $n$ let $M$ be an $n$ by $n$ matrix w/$0$'s on diagonal and natural numbers off diagonal and let $p_1, p_2, \dots, p_n$ be a set of prime numbers. Note then, that ...
4
votes
3answers
889 views

The last 2 digits of $7^{7^{7^7}}$

What is the calculation way to find out the last $2$ digits of $7^{7^{7^7}}$? WolframAlpha shows $...43$.
0
votes
2answers
72 views

Quick way to solve computational congruences

The specific problem at hand is $$34x \equiv 60 \bmod{98}$$ I reduced to get $$17x \equiv 30 \bmod{49}$$ and from this I have $$17x \equiv 30 \bmod{7}$$ which is easy to solve and yields $x \equiv 3 ...
1
vote
2answers
122 views

divisibility observation in particular patterns

Please look at the following observation made by trial and error. Let us take some $2$-digit numbers like $12, 15, 24,\dots$ $12 = 1 * 2 = 2 \implies 2|12 $ ($2$ divides $12$) $15 = 1 * 5 = 5 ...
1
vote
1answer
78 views

GCD of elementary symmetric functions

It is easy to show that p/ $\sigma_j$ ( where $\sigma_j$ is the sum of all products of j distinct members of the set {1,2,...,p-1}) for all $1 \leq j \leq p-2$, but how would you go about showing that ...
2
votes
1answer
135 views

Total no. of ordered pairs $(x,y)$ in $x^2-y^2=2013$

Total no. of ordered pairs $(x,y)$ which satisfy $x^2-y^2=2013$ My try:: $(x-y).(x+y) = 3 \times 11 \times 61$ If we Calculate for positive integers Then $(x-y).(x+y)=1.2013 = 3 .671=11.183=61.33$ ...
5
votes
2answers
125 views

Number Theory: $x^2+y^2=a^2$

Is there a coprime triple $(x,y,z)$ such that $x^2+y^2=a^2, x^2+z^2=b^2, y^2+z^2=c^2$, where $a,b,c$ are integers P.S. such solution doesn't exist for $a,b,c<1000$, as the computer says P.P.S. ...
1
vote
0answers
198 views

Evaluating a polynomial at a root of unity?

Let $R = \mathbb{Z}[x]/(x^n+1)$ be the $2n$th cyclotomic ring (for $n$ a power of $2$ in which case $\Phi_{2n}(x) = x^n+1$). Let $g$ be an $n$-dimensional vector chosen at random from $\mathbb{Z}^n$ ...
1
vote
2answers
181 views

Classify the odd primes $q$ such that a NEGATIVE number is a quadratic residue $\mod{q}$

Suppose we are given $y < -1$. I wish to classify all primes $q$ such that $y$ is a quadratic residue $\pmod{q}$, i.e. such that there exists a number $x$ satisfying $$y \equiv x^2 \pmod{q}.$$ How ...
2
votes
1answer
176 views

Finding a prime $p$ to solve a quadratic congruence $\pmod{p}$

I have a congruence of the form $$ax^2+bx \equiv -1 \pmod{p},$$ where $p$ is an odd prime and $a,b \in \mathbb{Z}$. Given $a$ and $b$, is there a general method to finding $p$ such that the above ...
8
votes
2answers
346 views

Compute the remainder when $67!$ is divided by $71$.

This is how far I've been able to get. By using Wilson's Theorem: $$\begin{align} 70! &\equiv -1 \pmod{71} \\ 67!(68)(69)(70) &\equiv -1 \pmod{71} \\ 67!(68)(69)(-1) &\equiv -1 \pmod{71} ...
2
votes
1answer
115 views

Pell's type equation in sum

I have an another observation on concatenation in sum. For instance, take $12^2 + 33^2 = 1233$. Find as many such pairs (x, y) with $x^2 + y^2 = xy\,$(here xy is concatenation)is possible. Also, ...
-2
votes
2answers
190 views

Use the modular exponentiation algorithm to find $13^{277} \pmod {645}$

I need to solve this question using the modular exponentiation method.
3
votes
1answer
113 views

$\sigma(\sigma(p^2)) \neq 2p^2$ for all odd primes $p$.

How to prove that $\sigma(\sigma(p^2)) \neq 2p^2$ for all odd primes $p$? I know that $\sigma(p^2)=1+p+p^2$ but I can't progress anymore.
1
vote
1answer
49 views

Using Fermat's little theorem to prove that $\sum_{i=0}^{n-3} (-1)^{i}a^{n-2-i}b^{i+1} = 1 + $ multiple of $n$

Using Fermat's little theorem, prove that $$ a^{n-2}b - a^{n-3}b^2 + a^{n-4}b^4 - \ldots + ab^{n-2} = 1 + M(n) $$ if $n$ is prime and doesn't divide $a$, $b$ or $a+b$ and $M(n)$ means a ...
2
votes
3answers
158 views

$2^n-3^m=1 , m,n \in \mathbb N =?$

$2^n-3^m=1 , m,n \in \mathbb N =?$ my questions are: do m,n exist? are they finitely many $m,n$? if there are infinitely many is there a way to describe them all? Same question about $3^n-2^m=1 $, ...
10
votes
2answers
364 views

A matrix w/integer eigenvalues and trigonometric identity

Any intuition and/or rigorous arguments on the proofs of the following statements would be appreciated: Let $n$ be a natural number. (a) Consider the following Toeplitz/circulant symmetric matrix: ...