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

learn more… | top users | synonyms (1)

10
votes
1answer
82 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
243 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
48 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
124 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 ...
0
votes
3answers
93 views

Product of two odd numbers is odd

How do I prove that the product of odd integers is odd? I know that I'm supposed to use an algebraic equation.
1
vote
1answer
73 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
164 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
27 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 ...
2
votes
1answer
101 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
35 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....
3
votes
0answers
31 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
71 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$, $gcd(c,ab) =...
2
votes
1answer
32 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
119 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
33 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
101 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
4answers
644 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
70 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 ...
0
votes
1answer
55 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
29 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 (...
10
votes
1answer
216 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
1answer
277 views

Solving a question about Fibonacci and Lucas numbers using induction

Im working on practice problems that the instructor gave us yesterday, and I absolutely have no clue of how to solve this problem.. I need to use mathmatical induction to solve this problem.. The ...
1
vote
1answer
33 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
43 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
59 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$ $y^...
2
votes
1answer
49 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
72 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 not ...
2
votes
2answers
54 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.
2
votes
0answers
81 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
23 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$ $a_{m,...
0
votes
1answer
32 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
1answer
44 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
57 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 $19$...
0
votes
2answers
52 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 far,...
6
votes
1answer
270 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
87 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 ...
5
votes
1answer
28 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
40 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 \...
2
votes
2answers
114 views

Define a relation on the integers such that $a R b$ iff $\;3\mid (a + 2b)$?

I've seen relations defined as functions between sets and as sets of ordered sets; however, I've never seen a relation defined as $3\mid(a+2b)$. What does this mean? --Edit-- I'll try and express my ...
3
votes
0answers
216 views

About the total number of twin primes in the vicinity of twin primes

Just for curiosity's sake, I did a test regarding twin primes, and I have doubts about the meaning of the results. Test: calculation of ${\pi_2}$(n) and the twin primes density in the vicinity of ...
3
votes
0answers
40 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$ ...
4
votes
2answers
72 views

Solve equation using Little Fermat's theorem

I'm trying to solve $8^x \equiv 2 \mod 23$ using Fermat's little theorem. We have $2^{3x} \equiv 2 \mod 23$, then $3x=23$, but this doesn't work. Could somebody please help?
6
votes
2answers
127 views

Possible values of infinitely nested square root $n= \sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x}…}}}$

If $$n= \sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x}......}}}$$ Is it possible that $n$ is a integer for any $x=Z( \text{zahlen number})$.If yes .What is the value of $x$??
0
votes
1answer
52 views

Prove that $\sqrt m$ is irrational by showing that the set $\{n\in\mathbb N: n\sqrt m\in\mathbb N\}$ is empty

Let $m\in\mathbb N$ be such that $m\neq k^2$ for all $k\in\mathbb N$. Prove that $\sqrt m$ is irrational by showing that the set $\{n\in\mathbb N: n\sqrt m\in\mathbb N\}$ must be empty.
2
votes
0answers
44 views

Prove $[(n, k)] = 7^{*} \iff n - k = 7$

Prove $[(n, k)] = 7^{*} \iff n - k = 7$ given $7^{*} = [(8,1)] \in \mathbb{Z}$ and $k < n \in \mathbb{N}$ using any facts about addition in the Peano System. $k < n \in \mathbb{N}$ is defined ...
4
votes
2answers
195 views

Bases required for prime-testing with Miller-Rabin up to $2^{63}-1$

This webpage (as well as Wikipedia) explains how one can use the Miller-Rabin test to determine if a number in a particular range is prime. The size of the range determines the number of required ...
1
vote
1answer
52 views

Proof verification: Proving that $\gcd(p,q,r)>1$

If gcd(p,q,r) = 1 Prove that there is an integer A such that gcd(p, q+Ar) = 1 Is the following proof good (correct)? If we assume for the sake of contradiction that $\gcd(p,q+Ar)$ $>1\ \forall A\...
1
vote
5answers
73 views

Let $n$ be a three digit number. Prove or give a counter example: $9|n$ if and only if the digits of $n$ sum to a multiple of $9$.

Let $n$ be a three digit number. Prove or give a counter example: $9|n$ if and only if the digits of $n$ sum to a multiple of $9$. I was able to go from left to right. But I'm having a hard time ...
0
votes
2answers
63 views

if $n$ is a Prime number and $\omega \neq 1$ then $1+\omega+\omega^2+…+\omega^{n-1}=0$

Let $n$ is a Prime number , $\omega \neq 1$ is a n-th root of unity , show that Other to form the n-th roots are $\omega ,\omega^2,...,\omega^{n-1}$ and we have $1+\omega+\omega^2+...+\omega^{n-1}=0$
2
votes
0answers
52 views

Conceptual question on showing properties of the absolute value function on $\mathbb{Q}$

I have a rather conceptual question about showing certain small lemmas regarding the absolute value function on $\mathbb{Q}$. I want to only give one example: Let $a,b \in \mathbb{Q}$ and $|.|$ ...