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

learn more… | top users | synonyms (1)

5
votes
3answers
117 views

prove that $2^n+2^{n-1}+2^{n-2}+8^n-8^{n-2}$ is a multiple of 7

Prove that a number $2^n+2^{n-1}+2^{n-2}+8^n-8^{n-2}$ is a multiple of 7 for every natural $n\ge2$. I am not sure how to start.
0
votes
2answers
108 views

Prepend a 9 or append a 0?

Given a positive integer $x$, will $x$ always be larger if one prepends a 9 in comparison to appending a 0? For x = 1, prepending is largest because $91 > 10$ For x = 9, prepending is largest ...
0
votes
1answer
34 views

How to compute n(mod c) when n(mod a),n(mod b),a,b,c are given?

Given a(prime) > b (prime) > c(any number), is there any way to compute n(mod c) ? n%a,n%b,a,b,c are known.
1
vote
1answer
23 views

Quadratic nonresidues mod p

The question asks to find congruence conditions on prime $p$ such that $7$ is the least quadratic nonresidue mod p. Also, find the least such prime. I solved it for $1,2,3,4,5,6$ mod $p$ and got ...
1
vote
1answer
27 views

Proving q is prime in the Legendre Symbol

Prove that if $p$ is an odd prime and if $q$ is the least integer such that $0$ < $q$ < $p$ and $\left(\frac qp\right)= -1 $, then q is prime. I've tried to solve it by contradiction. I ...
0
votes
1answer
21 views

Problem regarding quadratic reciprocity

Here is the question : Prove that if the prime $p\equiv 1\pmod4$ and $q$ is a quadratic nonresidue mod $p$, then the solutions of the congruence $x^2 \equiv -1\pmod p$ are $x\equiv \pm q^a\pmod ...
0
votes
1answer
23 views

modular multiplicative inverse of $2 \pmod {17}$

Find an inverse of $a$ modulo $m$ for $a=2, m=17.$ Applying euclidian algorithm: $\gcd(17,2)$ $17=8(2)+1$ $2=2(1)+0$ Expressed as a linear combination, this is $1=(1)17-8(2)$, and since the ...
0
votes
2answers
62 views

Chinese Remainder theorem, no inverse?

$$ \begin{cases} x\equiv 7&\pmod{9} \\ x\equiv4 &\pmod{12} \\ x\equiv16&\pmod{21} \end{cases} $$ Compute $m$, $9*12*21=2268$. Compute $M_1=$$m\over3$$=252$. Compute $M_2=189$. Compute ...
0
votes
1answer
89 views

Equality of equivalence classes for congruence modulo 7

Let R be the relation of congruence modulo 7. Which of the following equivalence classes are equal? [35], [3], [−7], [12], [0], [−2], [17] I got 3) [35] = [-7] = [0], [3] = [17], [12] = [-2] ...
0
votes
2answers
39 views

What steps are needed to solve $5x+80 = 13 \pmod 7$ and similar problems?

I am unsure of the steps needed to solve $$5x+80 = 13 \pmod 7$$ or this, $$31x=2\pmod{19}$$ I would like to see the steps necessary.
0
votes
3answers
67 views

x is divided by 3 and 4 implies its also divided by 6

I want to show that if $[3$ divides $x$ and $4$ divides $x]$ then $[6$ divides $x]$. I guess my starting point is something like $x=3n$ $x=4m$ But how do i show that there is also a $c$ with $x=6c$? ...
0
votes
1answer
58 views

Finding p in Legendre's symbol

The question is as follows: Find all odd primes $p$ such that $$\left(\frac 7p\right)=1$$ If the Legendre's symbol is flipped by quadratic reciprocity, we get $\left(\frac p7\right)=\pm1$. In this ...
3
votes
1answer
67 views

Statement about divisibility

Let's consider such function: $$f(N) = 1^1\cdot 2^2\cdot 3^3 \dots (N-1)^{N-1}\cdot N^N.$$ Does the expression $$\frac{f(N)}{f(r)\cdot f(N-r)}$$ is always integer? Can you give me any hint about ...
1
vote
1answer
92 views

Use division algorithm to prove for any odd integer n, $n^2 -1$ is a multiple of 8.

Here is what I know if n is any odd integer then $n$ can be expressed as $n=2k+1 ~~~ where~k\in\mathbb{Z}$.So $n^2-1=(2k+1)^2 -1=4k^2+4k=4k(k+1)$ but $k(k+1)~~ is~~even$. Thus $k(k+1)=2t, t\in ...
3
votes
3answers
130 views

How to compute the smallest integer which is sum of cubes in 13 ways?

I would like to know the smallest integer which is sum of three positive cubes in 13 ways, such that $1^3+2^3+3^3=2^3+1^3+3^3$ are same ways of representation? What kind of theory there is behind ...
4
votes
0answers
66 views

Prove $\forall n\in\mathbb{N}, \exists m\in\mathbb{N}; n=\pm1^2\pm2^2\pm\cdots\pm m^2.$

And we choose the positive and negative signs in a way that the equation becomes true. I think it can be proved with mathematical induction. So here's how I begin: For $n=1$, $1=+1^2$ which is true. ...
2
votes
2answers
102 views

Factoring numbers of the form $11111111$

Why $11111111$ is divisible by $73$? How can we get all the prime factors? It is clear that it is divisible by $11$. Is there any formulae for $1111...11$ ($n$ times)? Give me some idea. Thanks in ...
2
votes
2answers
65 views

Proof That,all the perfect squares each of which is the product of four consecutive odd natural numbers.

It's a question from the Bangladesh Mathematical Olympiad. It still haunts me a lot. I want to find an answer to this question. Find, with proof, all the perfect squares each of which is the ...
1
vote
3answers
62 views

Finding all prime numbers $p$ such that $p^a + p^b$ is a perfect square

Find all prime numbers $p$ and positive integers $a$ and $b$ such that $p^a + p^b$ a perfect square. How can I find this. I have no idea about this problem.
1
vote
1answer
55 views

The number $2^{3^n}+1$ is divisible by $3^{n+1}$ and not divisible by $3^{n+2}$.

Prove that for every $n\in \mathbb N$, $2^{3^n}+1$ is divisible by $3^{n+1}$ and not divisible by $3^{n+2}$. I was able to prove that $2^{3^n}+1$ is divisible by $3^{n+1}$ using induction. First, ...
1
vote
1answer
46 views

Find the Value of $n$ Where $15756$ is the $nth$ Member of A Set

It's a question from $BNMO$.It still haunts me a lot. I want to find an answer to this question. Any number of the different powers of $5: 1,5,25,125$ etc is added one at a time to generate the ...
0
votes
5answers
32 views

$x^2+3x+b=0$ has an integer solution (mod $17$) for which $b\lt 17$?

Find all non-negative integers $b<17$ such that the equation $x^2+3x+b=0$ has an integer solution (mod $17$). I know this is probably obvious. But I have no idea what to search for to find the ...
0
votes
1answer
45 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
62 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 ...
3
votes
2answers
106 views

Is the greatest common divisor injective? Is it bijective?

In an examination paper, there were the following questions: Is gcd an injective function? Is gcd a bijective function? I found these questions odd because I thought that we need to ...
2
votes
1answer
53 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)?$$
2
votes
1answer
82 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
79 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
80 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
104 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
31 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 ...
6
votes
2answers
104 views

Count with only certain digits allowed - And feel a fractal

I have a friend ~200 years old mathematician who has forgotten some digits and now he counts things in very strange manner: when he is going to count the $n$-th thing and $n$ contains a digit he ...
1
vote
1answer
63 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
92 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
23 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 ...
1
vote
1answer
77 views

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

(Note: This has been cross-posted to MO.) 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$). ...
1
vote
0answers
28 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 ≥ ...
3
votes
0answers
26 views

Properties of digit functions for numbers in $[0,1]$

Consider a function $g(n): \mathbb N \to \{0,1,2,3,4,5,6,7,8,9\}$, ie. $g$ maps the natural numbers to natural numbers between $0$ and $9$. Then, no matter what $g(n), \ n\in \mathbb N$ is, the sum ...
1
vote
1answer
35 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
31 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 ...
2
votes
5answers
94 views

Prove that if $3\mid n^2 $ then $3\mid n $. [duplicate]

$n \in \mathbb{N}$ Prove that if $3\mid n^2 $ then $3\mid n $ I want to prove this in a accepted formal way, I thought about the fact that every integer can be written as multiplication of prime ...
0
votes
0answers
32 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
51 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
187 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
56 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
48 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
27 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 ...
6
votes
0answers
86 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 ...
1
vote
1answer
29 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
32 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 ...