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

learn more… | top users | synonyms (1)

0
votes
2answers
22 views

How to show that $(2, \sqrt{82})$ in $\mathbb{Z}[\sqrt{82}]$ is not pricipal?

I tried the obvious things, like using the norm and trying to show that there were no integer solutions to $a^2 - 82b^2 = 2$, but didn't get anywhere. (A friend asked me this.)
0
votes
1answer
30 views

Integer solutions to $2x^2+5x+y^2=19$

$$2x^2+5x+y^2=19$$ Don't know how to approach the problem. Similar equations required factoring after the completing a square or a similar trick. I don't see the possibility of that here though. ...
2
votes
2answers
24 views

if $4^{\alpha} \equiv k+1 \pmod{2k+1}$ prove there is no $\beta$ where $4^{\beta} \equiv k\pmod{2k+1}$.

Suppose that $3 \nmid 2k+1$ and there is $\alpha$ with $4^{\alpha} \equiv k+1 \pmod{2k+1}$ where $0 \leq \alpha \leq k$. I want to prove that there is no $\beta$, $0\leq \beta \leq k$ such that ...
4
votes
0answers
36 views

theorem relating mersenne numbers?

For $(x2^9)^2=2^q-1+y^2q^2$,where $q$ is prime, is it possible to show that there exists only an unique solution for the pair $\{x,y\}$?
5
votes
2answers
75 views

$3^x + 4^y = 5^z$

This is an advanced high-school problem. Find all natural $x,y$, and $z$ such that $3^x + 4^y = 5^z$. The only obvious solution I can see is $x=y=z=2$. Are there any other solutions?
0
votes
0answers
18 views

If $q^k n^2$ is an odd perfect number with Euler prime $q$, are the following statements known to hold in general?

(Note: This question has been cross-posted from MO.) Let $\sigma$ be the classical sum-of-divisors function. A number is said to be perfect if $\sigma(N)=2N$. If $q^k n^2$ is an odd perfect number ...
1
vote
0answers
46 views

Help with the results of a test about the distances between prime numbers

I did the following test: For every prime, take the distance $dp$ to the previous prime and the next prime $dn$, then calculate $a=(pp\ mod\ dp)$ and $b=(np\ mod\ dn)$. If $a$ or $b$ $\in \Bbb ...
1
vote
1answer
26 views

If $a \equiv b \mod m$ and $0 \leq a$ and $b < m$, $a=b$?

I was reading Hodel's otherwise excellent An Introduction to Mathematical Logic and, in the appendix on number theory, specifically on the section on congruences, he seems to make a slip. Let $a, b, m ...
3
votes
2answers
27 views

How to tell if a set of simultaneous congruences is solvable?

Let's say we have a set of N simultaneous congruences that looks like this: x ≡ c1 (mod m1) x ≡ c2 (mod m2) ... x ≡ cN (mod mN) Currently, to check if this set has a solution I have to go ...
0
votes
2answers
48 views

A question about Quadratic residue

I need help with this question : Prove that for each prime number p there exist $a,b \in Z$ such that $-1\equiv a^{2}+b^{2}\pmod p $ When $p\equiv1\pmod4$ it is easy because -1 is a quadratic ...
0
votes
1answer
37 views

Find the lowest value of $x$ so that $x \in (A \setminus B)$

Let $A$ and $B$ be two sets for which the following applies: $A = \{x: \text{GCD(}x,12) = 1\}$ $B = \{x: x\ \text{is a prime}\}$ Find the lowest value of $x$ so that $x \in (A \setminus B)$. $x \in ...
2
votes
1answer
63 views

Can the expression $6^{2n} - 25$ be a prime for all $n \geq 2$?

Can the expression $6^{2n} - 25$ be a prime for any $n \geq 2$? My attempt to solve the problem: No, it cannot. $6^{2n} - 25 = (6^{n})^{2} - 25 = (6^{n})^{2} - 5^{2} = (6^{n} + 5)(6^{n} - 5)$ And ...
10
votes
2answers
126 views

Determining if a number is a prime

Consider $$ x = \frac{4^{99}\cdot7 - 1}{3} $$ Is $x$ prime ? Why not ? I tried the divisibility criteria, but I can't find a way. I'm currently dabbling in number theory, but I got stuck on this one. ...
0
votes
2answers
33 views

How to prove the Archimedean property?

The archimedean property states that $$\boxed{~\forall~ ~a,b\in \mathbb{Z}^+~ \exists ~n~|~na\geq b~}$$ I started with disproving .. Suppose $\forall ~\{n,a,b\} \subset \mathbb{Z}^+ , \text{na ...
-1
votes
1answer
28 views

Let $A$ be an uncountable set and let $B$ be a nonempty set. Prove that the cardinality of $A\times B$ is uncountable. [on hold]

If $A$ is an uncountable set and $B$ is a nonempty set, how do I prove that $A\times B$ is uncountable? Also, what is the cardinality of $A-B$? Is it also uncountable?
2
votes
0answers
45 views

On splitting a number as the sum of two squares.

From Lagranges'celebrated four-squares theorem we know that any number is the sum of four squares ( not necessarily nonzero and distinct). But it's an existence theorem and gives no idea of how to ...
2
votes
1answer
57 views

Proof that if $a^3 \mid b^2$ then $a\mid b$. [duplicate]

I am trying to prove that if $a^3 \mid b^2$ then $a\mid b$, where $a,b \in \mathbb{Z}$. Let $PDC(x)$ be the set of all primes in the prime decomposition of $x$. So far, I am using the fundamental ...
1
vote
1answer
23 views

Proving $\gcd(N^a-1,N^b-1)=N^{\gcd(a,b)}-1$.

I have come by one solution only, but things were derived too quickly without me understanding how or why. How does knowing that $\gcd(a,b)$ is a factor and a and b, actually derive that ...
0
votes
1answer
26 views

Show that $a^{p+1\over 4}$ solves the equation $x^2 ≡ a \pmod p$.

Let $p \equiv3 \pmod 4$ be a prime number, and let $1 \le a\le p − 1$ be a quadratic residue. Show that $a^{p+1\over 4}$ solves the equation $x^2 ≡ a \pmod p$. I know that if $(a,n)=1$ and $p\ge ...
3
votes
0answers
34 views
+50

Does there exists a positive $t$ that satisfy this given condition?

I am curious about the validity of my claim concerning the equations: $(2k-1)t+1$ (1) $(2k^2-2k)t+(2k-1)$ (2) where $k=2,3,4,...$ My claim is for almost all $k$ or for infinitely many $k$, there ...
2
votes
2answers
23 views

Set of all integer solutions to a linear diophantine equation

I am trying to figure out the set of all integer solutions in terms of an appropriate number of free variables for the following: $2x_1 + 12x_2 + 3x_3 = 7$. I have found that the $gcd(2,12,3) = 1$ ...
1
vote
3answers
32 views

How to solve a congruence using Fermat's Theorem?

I'm reading Fraleigh's A First Course in Abstract Algebra and I'm trying to understand an example (later I have to solve several problems of the same type). Little Theorem of Fermat: If $a\in ...
3
votes
1answer
29 views

If $q^k n^2$ is an odd perfect number with Euler factor $q^k$, can $q = 73$ hold?

Call a number $N$ perfect if $\sigma(N)=2N$ where $\sigma$ is the classical sum-of-divisors function. If $N = q^k n^2$ is an odd perfect number, can $q = 73$ hold? Here is my attempt: Since ...
2
votes
1answer
61 views

Can any partial harmonic sum be an integer?

There have been a number of posts about the harmonic series, e.g. not being an integer for any number of terms. Edit: Below I try to prove that not only H(n) but also H(2n)-H(n) is not an integer. ...
1
vote
1answer
24 views

What are the most important corollaries/consequences and applications of certain algorithms in elementary number theory? [on hold]

What are the most important corollaries/consequences and applications of Division Algorithm, Euclidean Algorithm and Fundamental Theorem of Arithmetic? I've been studying Elementary Number Theory for ...
1
vote
1answer
18 views

Is it possible to compute $\sigma(AB)$ if $\gcd(A, B) = C > 1$?

Let $\sigma$ be the classical sum-of-divisors function. I know, for one, that $\sigma$ is weakly multiplicative (that is, $\sigma(xy) = \sigma(x)\sigma(y)$ whenever $\gcd(x, y) = 1$). Well, of ...
6
votes
5answers
88 views

Inductively prove that any natural number $\ge 12$ can be written as the sum of 4s and 5s

I can intuitively see why this is true: Let us assume $n = \alpha \times 4 + \beta \times 5$ with $\alpha,\beta \in \mathbb{N} \cup \{0\}$. $\forall n \in \mathbb{N} \cup \{0\}$: $n \div 4$ will ...
0
votes
1answer
22 views

Let $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$, suppose $ax \equiv 1 \mod n$. Prove $a$ is coprime to $n$.

Let $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$, suppose $ax \equiv 1 \mod n$. Prove $a$ is coprime to $n$. How do I do this? I know so far that $ax=1+nk ~(k \in \mathbb{Z})$.
2
votes
2answers
57 views

Finding the solutions of $x^2\equiv 9 \pmod {256}$.

Find the solutions of $x^2\equiv 9 \pmod {256}$. I try to follow an algorithm shown us in class, but I am having troubles doing so. First I have to check how many solutions there are. Since $9\equiv 1 ...
-4
votes
0answers
25 views

How to find two numbers given their sum of squares, HCF and LCM? [on hold]

if sum of squares of two numbers are 2754,HCF is 9,LCM is 135...what are the numbers?
-1
votes
3answers
32 views

How to find two numbers given their difference, HCF and LCM? [on hold]

The difference of two numbers is 14. Their LCM and HCF are 441 and 7 respectively. Find the numbers. Any shortcuts please. Thanks in advance.
3
votes
1answer
31 views

Proof by induction from Spivak's calculus ch 2- 3b

I was cracking my head over the following proof (by induction) from Spivak's calculus. Givens: $ \binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k} $ and $ n \ge k $ Task: Proof by induction that $ ...
3
votes
2answers
26 views

Let $X$ be a set of primes $p$ so that $5^{p^2}+1 \equiv 0 \pmod {p^2}$ Which of these sets is $X$ equal to?

$5^{p^2}+1\equiv 0\pmod {p^2}$ $1.$ $\emptyset $ $2.$ {$3$} $3.$ All primes of the form $4k+3$ $4.$ All primes except $2$ and $5$ $5.$ All primes This one is pretty easy to get right through the ...
1
vote
0answers
14 views

Number of number in range $(l, r)$ satisfying XOR constarint

Here's a questions that's been bugging for some time now: Define the set $S_n = \{k \oplus (k + n)\mid k \in \Bbb Z, k ≥ 0\}$ (here, $\oplus$ is bitwise exclusive OR). To put it another way, $x$ ...
1
vote
2answers
67 views

Why is $ {n\choose k} \equiv 0 \pmod n$ if $n$ is prime? [duplicate]

For all $n>k$, why is: $$ {n\choose k} \equiv 0 \pmod n$$ if $n$ is prime? Any hints anyone? I am really puzzled.
1
vote
2answers
47 views

Legendre symbol, a theoretical question.

I need to show that if $p$ is a prime number of the form $p=4m+1$, then for any divisor $d$ of $m$: $$\left(\frac{d}{p} \right) = 1$$ where $\left(\frac{d}{p} \right)$ is the Legendre symbol. My ...
1
vote
2answers
46 views

Show that the equation $x^2\equiv a \pmod n$ is solvable $\iff$ $a^{\phi (n)\over 2}\equiv 1\pmod n$.

Let $n> 2$ be an integer such that $(\Bbb{Z}/n\Bbb{Z})^*$ has a primitive root. Show that the equation $x^2\equiv a \pmod n$ is solvable $\iff$ $a^{\phi (n)\over 2}\equiv 1\pmod n$. I thought I ...
0
votes
1answer
23 views

Let $n \in \mathbb{N}$ and consider the commutative ring $\mathbb{Z}_n$. Let $a \in \{1,2,…,n-1,n\}$…

Let $n \in \mathbb{N}$ and consider the commutative ring $\mathbb{Z}_n$. Let $a \in \{1,2,...,n-1,n\}$. Suppose $a$ is coprime to $n$ then prove $\bar{a} \in \mathbb{Z}_n$ is a unit. Note ...
1
vote
2answers
36 views

A set of numbers

Problem: Let $E(x)$ be the number defined by the following expression \begin{equation*} E(x)=\sqrt[3]\frac{x^3-3x+(x^2-1)\sqrt{x^2-4}}{2}+\sqrt[3]\frac{x^3-3x-(x^2-1)\sqrt{x^2-4}}{2} \end{equation*} ...
3
votes
1answer
19 views

How to proceed with Euclidean algorithm for finding greatest common divisor of two polynomials.

I am trying to find \begin{equation*} gcd(x^4-x^3-4x^2-x+5,x^2+x-2). \end{equation*} I have done the first step of long division and found. \begin{equation*} x^4-x^3-4x^2-x+5=(x^2-2x)(x^2+x-2)-5x+5 ...
3
votes
1answer
22 views

The necessary and sufficient condition for a regular n-gon to be constructible by ruler and compass.

I have a problem concerning the necessary and sufficient condition for a regular n-gon to be constructible by ruler and compass. $\bf My$ $\bf question:$ For a given positive integer $n$, how can we ...
0
votes
0answers
26 views

Prove: If $p \in \mathbb{N}$, $p$ is prime and $p\mid ab$ then $p\mid a$ or $p\mid b$. [duplicate]

Theorem 1. If $p \in \mathbb{N}$, $p$ is prime and $p\mid ab$ then $p\mid a$ or $p\mid b$. I am stuck on this proof here is what I have done so far: Proof of Thm 1. $p\mid ab \implies ...
0
votes
2answers
40 views

Find the number of possible values of $a$

Positive integers $a, b, c$, and $d$ satisfy $a > b > c > d, a + b + c + d = 2010$, and $a^2 − b^2 + c^2 − d^2 = 2010$. Find the number of possible values of $a.$ Obviously, factoring, ...
1
vote
1answer
25 views

A question about $\gcd$ and divisibility

Let $\sigma$ be the classical sum-of-divisors function. Suppose that I have the following equations: $$2n^2 - \sigma(n^2) = \frac{\sigma(n^2)}{q^k}\cdot{\sigma(q^{k-1})}$$ $$2n^2 - \sigma(n^2) = ...
3
votes
1answer
25 views

What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$?

Let $\sigma$ denote the classical sum-of-divisors function. What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$? Update: I have transferred the transcript of my attempt to an actual answer to this MSE ...
0
votes
1answer
15 views

How many rows & columns do 1,028 equal spaces create…

I have a board that is 17.5" wide and 67" long. I need to divide this board into 1,028 equal spaces. How many rows and how many columns will this equate to?
5
votes
1answer
54 views

How can I prove the Carmichael theorem

I am trying to prove that these two definitions of Carmichael function are equivalent. I am using this definition of Carmichael function: $\lambda(n)$ is the smallest integer such that ...
1
vote
4answers
63 views

$6^{66}\equiv r \pmod {66}$

The answer doesn't need to be exact, the possible answers to the exercise are "between 30 and 40", "from 50 to 66" or something akin to that. I've no idea how to solve this. Previous problems of this ...
0
votes
2answers
43 views

Prove: $\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$ [duplicate]

I'm trying to prove the following statement: $$\forall_{a,b\in\Bbb{N^{+}}}\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$$ As for now I managed to prove that $n^{\gcd(a,b)}-1$ divdes $n^a-1$ and $n^b-1$: Without ...
0
votes
1answer
26 views

General question on notations when dealing multiplicative and additive modulo

One of the property for the requirement for a set to be a group is associativity. Under ordinary multiplication: $\large{a(bc)=(ab)c}$ Under ordinary addition: $\large{a+(b+c)=(a+b)+c}$ What ...