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

learn more… | top users | synonyms

0
votes
1answer
42 views

suppose for $a$ and $b$ we have $(a,b)=1$ ,show that the biggest common divisor of $a^2+b^2$ and $2ab$ is 1 or 2.

suppose for $a$ and $b$ we have $(a,b)=1$ ,show that the biggest common divisor of $a^2+b^2$ and $2ab$ is 1 or 2. I did some elementary calculation on the property of bcd but no good success will ...
0
votes
2answers
46 views

modulo of a large number

I need help with solving modulo of large numbers, wondering if it is possible to compute the answer without the use of calculator. for example: 545^112 (mod 23) how can this be solved? I reduced my ...
-5
votes
3answers
50 views

How many numbers less than 10000 are there which are divisible by 21, 35, 63?

I am trying to determine: How many numbers less than $10000$ are there which are divisible by $21$, $35$, $63$? To be clear, let me add that I want numbers that are divisible by each of $21$, ...
2
votes
2answers
68 views

Questions on gcd (greatest common divisor)

In an examination paper, there were the following questions: 1. Is gcd an injective function? 2. Is gcd a bijective function? I found these questions odd because I thought that we need to first know ...
1
vote
1answer
21 views

Legendre's symbol negative sign

If $a=-2$ in the legendre symbol $\left(\frac ap\right)$, can we take out the negative sign so that the symbol can be written as $$-\left(\frac 2p\right)?$$
0
votes
0answers
23 views

An example for Liouville's theorem (1844)?

This Liouville's theorem (the most unknown of his work) : "If $n \in \mathbb{N^{*}}$ and $p>5$ a prime number, then the equation $(p-1)! + 1 = p^{n}$ has no solution." The standard proof is clear. ...
3
votes
2answers
73 views

Nonlinear diophantine equations $x^2+2y=z^2$ and $y^2+2x=w^2$

I am asked to find two sets of positive numbers $x$ and $y$, such that both $x^2+2y$ and $y^2+2x$ are perfect squares. I found a general solution to either single equation, but it seems impossible ...
10
votes
1answer
74 views

Equation $(a+b)^a=a^b$

How can we find the positive integer solutions to $(a+b)^a=a^b$? Since $a+b>a$, it is necessary that $a<b$, otherwise the left-hand side is less than the right-hand side. So let $b=a+x$. The ...
2
votes
1answer
60 views

Proof of Euler's Totient Theorem

I have seen quite a few proofs of Euler's Totient Theorem that $a^{\phi(n)}≡1 \pmod n$ for all $a$ relatively prime to $n$. However, none have been done using induction. That is what I have been ...
1
vote
1answer
16 views

Odd Integers in Different Bases

Show that an integer in an odd base is odd in base 10 if and only if it has an odd number of odd digits. For example, $223_{base5} = 50+10+3=63_{base10}$. Intuitively, this makes perfect sense, but ...
1
vote
0answers
40 views

Any heuristic explanation on why sieve methods can not prove Goldbach conjecture?

Any heuristic explanation on why sieve methods can not prove strong Goldbach conjecture ? I remember that Terence Tao published a blog and gave an heuristic explanation on why circle methods very ...
-4
votes
1answer
133 views

Find point after Kth turn

Given a segment from $[0, X]$ and no points marked on it. On each step we choose the sub segment of maximal length possible such as it contains no points on it. If there are more than one such sub ...
1
vote
1answer
57 views

Legendre's symbol conditions on prime p

The question: What are the necessary and sufficient conditions on $p$ for which the legendre symbol $$\left(\frac 5p\right)= 1 ?$$ PS: $p$ is an odd prime
1
vote
4answers
62 views

positive fractions, denominator 4, difference equals quotient

(4,2) are the only positive integers whose difference is equal to their quotient. Find the sum of two positive fractions, in their lowest terms, whose denominators are 4 that also share this same ...
0
votes
1answer
20 views

Equivalence relation of legendre symbols

The question states that p is a prime of the form $4k+1$. Using this prove the follwowing: $$\left(\frac ap\right)=\left(\frac qp\right)$$ where $q=p-a$. I tried to simply replace $p$ but that doesn't ...
0
votes
1answer
21 views

Improving the bound $q < n\sqrt{3}$ for an odd perfect number $N = {q^k}{n^2}$ given in Eulerian form

Let $N = {q^k}{n^2}$ be an odd perfect number given in Eulerian form (i.e., $q$ is prime with $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q, n) = 1$). Therefore, $q \neq n$. It follows that either $q ...
1
vote
0answers
21 views

p ∈ P, r ∈ Z s.t. p does not divide r. Show that if X2 − r ≡ 0(mod p) has a solution a ∈ Z, then X2 − r ≡ 0 (mod p e ) has a solution for every e ≥ 1.

Let $p ∈ P$ be an odd prime, and let $r ∈ Z$ such that $p$ does not divide $r$. Show that if $X^2 − r ≡ 0\pmod p$ has a solution $a ∈ Z$, then $X^2 − r ≡ 0 \pmod {p^e}$ has a solution for every $e ≥ ...
1
vote
1answer
27 views

Conclude that the multiplicative order modulo $ab$ of any $c$, $gcd(c,ab) = 1$ must be a proper divisor of $\phi(ab)$.

a) Show that if $n = ab$ where $1 < a, b$ are odd and $gcd(a,b) = 1$, then $lcm(\phi(a),\phi(b)) < \phi(ab)$. b) Conclude that the multiplicative order modulo $ab$ of any $c$, ...
2
votes
1answer
26 views

Show that n is a perfect square if and only if $k_i$ is even for $ 1 \leq i \leq m$

Suppose that $n = p_{1}^{k_1} p_{2}^{k_2} ... p_{m}^{k_m}$, where $p_1<p_2<...<p_m$ are all prime. Show that n is a perfect square if and only if $k_i$ is even for $1 \leq i \leq m$ I'm not ...
0
votes
0answers
28 views

Does this “distribution of factors” cover all possibilities?

I have the Diophantine equation $$3a^2(4a^2+1)=b(b+1). \tag{$\star$}$$ Each side can evidently be “separated” into two [integer] factors as $$3a^2 \cdot (4a^2+1) = b \cdot (b+1).$$ Now I believe I ...
1
vote
0answers
29 views

Solvability of a quadratic congruence modulo $p^{k}$

Let $p$ be an odd prime number and let $a$ be an integer where $p$ and $a$ are relatively prime. If $k$ is a positive integer, prove that the congruence $x^{2} ≡_{p^{k}} a$ is solvable if and only if ...
2
votes
3answers
84 views

Primes dividing $11, 111, 1111, …$

How can I prove that every prime except 2 and 5 divide infinitely many of the following integers $11, 111, 1111, ...$ ?
-1
votes
1answer
42 views

Determine the mod 5^3 roots of F(X) = 5X^3 + X^2 - 1 using Hensel's lemma

Determine the mod 5^3 roots of F(X) = 5X^3 + X^2 - 1 using Hensel's lemma. So far I have: F'(X) = 15X^2 + 2X. The mod 5 roots of F(X) are 1 and 4, bc 5|F(1)=5 & 5|F(4)=335 so the next step is ...
2
votes
1answer
37 views

Problem regarding summation of the Legendre symbol

I'm trying to calculate the following: $$\sum_{a = 1}^{p - 1}\left(\frac ap\right)$$ The value given for $p$ is fairly large and I can't individually calculate the symbol for all the numbers. However, ...
4
votes
0answers
23 views

Connection or coincidence?

Here are two lemmas, one from number theory and one from finite reflection groups. 1) [HW,p.74] Let p be an odd prime. Partition the least nonzero residues (mod p) into positive (P) and negative ...
0
votes
0answers
20 views

Any results to generalize weighted sieve to three parameters?

In Chen's theorem on Goldbach conjecture , he used two parameter weighted sieve method, and he proved every even number can be represented as a prime number and an almost prime ( 1 + 2 ). Are there ...
5
votes
0answers
39 views

If $a$ is a quadratic residue modulo every prime $p$, it is a square - without using quadratic reciprocity.

The question is basically the title itself. It is easy to prove using quadratic reciprocity that non squares are non residues for some prime $p$. I would like to make use of this fact in a proof of ...
0
votes
2answers
44 views

I want to prove $1^{p-1} + 2^{p-1} + \cdots + (p-1)^{p-1} \equiv -1 \mod p$ [closed]

I want to prove that $$ 1^{p-1} + 2^{p-1} + \cdots + (p-1)^{p-1} \equiv -1 \mod p $$ where $p$ is a prime using elementary ways. How can I prove it ?
0
votes
0answers
13 views

Use of Prime Power Factorization

I think that I may not be understanding the use of prime decomposition of integers: If two integers $a=p_1^{j_1}...p_n^{j_n}$, $b=p_1^{k_1}...p_n^{k_n}$ are factored into primes, $b|a$ iff $k_i \leq ...
1
vote
1answer
27 views

Given $\gcd(d,d')=1, d\mid n, d' \mid n$, show that $dd' \mid n$

Given $d,d'$ are in $\mathbb{Z} > 1$, and $\gcd(d,d')=1$, and $d \mid n$ and $d'\mid n$, Show that $d\cdot d'\mid n$. I pretty much have it but I think it could be made more clear. I have: $d ...
2
votes
1answer
28 views

Basic question: what does this mean: polynomial $f(x) \in \mathbb{Z}[x]$ has a root mod $d$?

What does "A polynomial with coefficients in $\mathbb{Z}$ has a root of mod $d$" mean? I'm not quite sure what this means, my search has led me to a few slightly different answers. I'd love to see an ...
0
votes
2answers
41 views

Are the solutions of $x^2 = -y^2 \mod n$ always based off of $x^2 = -1 \mod n$

We know that if $x_i^2 = -1 \mod n$ we are able to find more solutions of the form, $x^2 = -y^2 \mod n$ Simple Proof: Let $x_i$ be the initial solution to $x_i^2+1 \equiv 0 \mod n$ ...
0
votes
0answers
30 views

Prove that the cube root of 2 is not a constructible number

So this is what I have done so far: Proof by Contradiction. Construct a cube with side length y whose volume is twice x^3 (where x is a constructible number) If you could construct y, then since y = ...
1
vote
1answer
35 views

Partitioning a finite set which sums to $n$

Given $n > 1$, we consider the finite sets of positive integers which sum to $n$, and out of these sets we want to maximize the product. For example, given $n = 6$, the set $\{1, 5\}$ does not ...
1
vote
5answers
56 views

Remainder when $p$ is divided by $6$

Let $p$ be a prime. If there is a remainder of $1$ on division of $p$ by $3$, then what is the remainder when $p$ is divided by $6$? why? I know the remainder is $1$ in both the cases, but I'm ...
1
vote
2answers
45 views

Prove that if $p$ is a prime and $p|k^n$, then $p^n|k^n$

I want to prove that if $p$ is a prime and $p|k^n$, then $p^n|k^n$ but I have no idea where to start.
3
votes
0answers
55 views

Diophantine $7^a+2=3^b$

I want to find the solutions $(a,b)\in\mathbb{Z}^+\times\mathbb{Z}^+$ of $7^a+2=3^b$. One such solution is $(a,b)=(1,2)$. Looking modulo $4$, we have $(-1)^a+2\equiv(-1)^b$, so $a$ and $b$ are of ...
0
votes
0answers
9 views

eulerian numbers problem

Eulerian Numbers(recursively defined; permutations of #'s 1-m with k ascents; ascent is 2 #'s in a row increasing): $a_{m,k}=(m-k)a_{m-1,k-1}+(k+1)a_{m-1,k},\quad 0\le k\le m-1\quad a_{0,0}=1$ ...
1
vote
1answer
25 views

Proving that $\varphi(n)$ is divisible by $\varphi(n_1)$ and $\varphi(n_2)$

So, I've been thinking about trying to prove this statement - If $n=n_1n_2$ and $n_1$ and $n_2$ are relatively prime integers greater than 2, prove both $φ(n_1)$ and $φ(n_2)$ divide $φ(n)$. In ...
2
votes
0answers
23 views

Equivalent condition for the divisibility by $2^{n-1}$.

I guess that the equivalent condition that for any positive integer $n,m$ $$ \sum_{k \ge 0} \binom {n}{2k} m^k $$ is divisible by $2^{n-1}$ is that $$m \equiv 1(mod 4).$$ Would you explain the reason ...
2
votes
3answers
46 views

What is the solution of the following congruency

Well, I tried to solve this equation. I think, that I have to work with the Chinese remainder theorem. $$73x \equiv 1 \pmod{247} $$ $247=13×19$ so I may have to check the modulo $13$ and modulo ...
1
vote
2answers
46 views

A proof involving Fermat's Little Theorem.

Let $p$ be a prime and n be an integer such that $p$ does not divide $n$. Suppose $d$ is the smallest natural number such that $n^d$ is congruent to $1 \mod p$. Prove that $d$ divides $(p-1)$. So ...
5
votes
1answer
69 views

Numbers as sum of distinct squares

Yesterday Polish Olympiad of Information Science ended, one of the questions was purely mathematical, Squares (PL). In the task, we have defined square ...
2
votes
2answers
39 views

Are there no even squares expressible as the sum of two prime squares?

When I was playing around with different number sequences, I noticed that I couldn't find any even squares that are expressible as the sum of two prime squares. Is this true, and is this related to ...
0
votes
2answers
28 views

True or false: $2a ≡ 2b \mod m ⇒ a ≡ b \mod m.$ [closed]

$$2a \equiv 2b \pmod m \;\rightarrow \;a \equiv b \pmod m$$ True or false ? Thanks
5
votes
1answer
20 views

Using two congruences and gcd

Prove that if $b_1, b_2 \in \mathbb Z$ and $d_1, d_2 \in \mathbb Z^+$, then there exists at least one solution $x \in \mathbb Z$ satisfying simultaneously: $x \equiv b_1 ($mod $d_1)$ $x \equiv b_2 ...
2
votes
1answer
26 views

Show that $a \equiv b$ (mod $n$) if and only if $r = s$.

Let $a, b \in \mathbb{Z}$ and let $n \in \mathbb{N}$. Write $a = qn + r$ and $b =q'n+s$ with $q,q' \in \mathbb{Z}$ and $r, s \in \{0,1,\ldots,n-1\}$ according to the divion algorithm. Show that $a ...
3
votes
1answer
116 views

At which p-adic fields does the equation have no rational solution?

I have to check if the equation $3x^2+5y^2-7z^2=0$ has a non-trivial solution in $\mathbb{Q}$. If it has, I have to find at least one. If it doesn't have, I have to find at which p-adic fields it has ...
3
votes
0answers
39 views

What is the relationship between GRH and Goldbach Conjecture?

We know that we can prove weak Goldbach Conjecture (three prime theorem) if we assume GRH (Hardy-Littlewood had proved this). Can we also prove strong Goldbach Conjecture if we assume GRH ? Also, ...
3
votes
0answers
29 views

Is this “by symmetry” statement valid?

Problem: Let $p,q,r$ be integers such that $\gcd(p,q,r)=1$. Prove that there exists an integer $A$ such that $\gcd(p,q+Ar)=1$. A start: Assume for the sake of contradiction that $\gcd(p,q+Ar)>1$ ...