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

learn more… | top users | synonyms

4
votes
3answers
100 views

The sum of the primes, p, that satisfy the condition that $8^p+15^p$ is a perfect square.

Well, the question is so: Suppose P is the set of all primes, p, that satisfy the condition that $8^p+15^p$ is a perfect square. Find the sum of the elements of P. Now, over here, I found out a few ...
2
votes
1answer
170 views

multiple approaches/ways to prove that $1000^N - 1$ cannot be a divisor of $1978^N - 1$

Am interested in learning to do multiple proofs for the same problem, and hence I chose this problem: Prove that for any natural number $N$, $1000^N - 1$ cannot be a divisor of $1978^N - 1$. ...
19
votes
5answers
1k views

Number of consecutive zeros at the end of $11^{100} - 1$.

How many consecutive zeros are there at the end of $11^{100} - 1$? Attempt Trial and error on Wolfram Alpha shows using modulus shows that there are 4 zeros (edit: 3 zeros, not 4). Otherwise, I have ...
2
votes
1answer
157 views

Number combination which brings different result in sum

I am looking for 6 numbers which when added their sum should not be a repeated no like one below for 3 Numbers Num 1 Num 2 Num 3 Sum 1 3 5 9 1 ...
5
votes
0answers
159 views

Carmichael number factoring

The task I'm faced with is to implement a poly-time algorithm that finds a nontrivial factor of a Carmichael number. Many resources on the web state that this is easy, however without further ...
8
votes
3answers
208 views

Counting Different Ways of Summing Numbers

I am looking for information on counting the possible ways of summing numbers. For example, suppose you can use 1,2, and 4. How many possible combinations are there to create any number? For ...
6
votes
3answers
220 views

Quadratic congruence

There is question For each of prime $p$, show that the congruence $x^2 \equiv1 \pmod {p^a}$ has precisely two solutions. Continue and show that the congruence $x^2 \equiv 1 \pmod ...
4
votes
3answers
77 views

Every residue class $\pmod{2^a}$ can be written as $\pm 5^r$ for some $r$

So the question is to show that every residue class $\pmod{2^a}$ can be written as $\pm 5^r$ for some $r$. The hint is to first show that: For $a \ge 3$, and $H$ the multiplicative subgroup of ...
2
votes
1answer
86 views

Convergent sum involving the divisor function

Here's a doosy posed as a challenge question; Let $d(n)$ be the number of divisors of $n$. Prove that $d(n)$ is a multiplicative function of $n$ and show that for any natural number $r \ge 1$, the ...
3
votes
1answer
68 views

$5^{2^{a-3}} \equiv 1+2^{a-1}\pmod{2^a}$

Here's a tricky question I have in a homework problem: Via induction, show $5^{2^{a-3}} \equiv 1+2^{a-1}\pmod{2^a}$ and then deduce that $5\pmod{2^a}$ has order $2^{a-2}$ for $a \ge 3$ Help please ...
5
votes
2answers
69 views

Showing that $(\mathbb{Z}/p^a \mathbb{Z})^*$ has order $p^{a-1}(p-1)$.

Showing that $(\mathbb{Z}/p^a \mathbb{Z})^*$ has order $p^{a-1}(p-1)$ where $p$ is prime. This for a class on elementary number theory, so this question caught me off-guard having only minor ...
0
votes
2answers
87 views

Check which $a$ has a square root modulo $p$ for each $a$ and $p$ below:

Check which $a$ has a square root modulo $p$ for each $a$ and $p$ below: $(a) a=3\space \text{and}\space p=11$ $(b) a=-1\space \text{and}\space p=59$ $(c) a=36\space \text{and}\space p=37$ I feel ...
5
votes
6answers
185 views

If $d^2|p^{11}$ where $p$ is a prime, explain why $p|\frac{p^{11}}{d^2}$.

If $d^2|p^{11}$ where $p$ is a prime, explain why $p|\frac{p^{11}}{d^2}$. I'm not sure how to prove this by way other than examples. I only tried a few examples, and from what I could tell $d=p^2$. ...
0
votes
0answers
89 views

Proving a simple inequality

Can someone show that the inequality bellow holds? $$ f(n) \leq f(n+1) \ $$ Where $$ \frac{\sum\limits_{k=1}^n \Lambda(k) {k}/{n}\lceil{n}/{k}\rceil{}\{ n/k \}}{\sum\limits_{k=1}^n \Lambda(k)}=f(n)$$ ...
4
votes
1answer
133 views

explain why $a^{\frac{p-1}{2}}\equiv 1 \pmod{p}$.

If $\gcd({a,p})=1$ where $p\gt2$ is a prime and if $a$ has a square root modulo p, explain why $a^{\frac{p-1}{2}}\equiv 1 \pmod{p}$. I wish I could provide some work, but all i've been able to find ...
1
vote
3answers
977 views

modulo version of the quadratic formula and Euler's criterion

Use the modulo version of the quadratic formula and Euler's criterion to decide if the following has a solution or not. $2x^2+5x+8 \equiv 0\pmod{37}$ I'm not sure how I would use what was being ...
2
votes
5answers
151 views

Prove that $\forall n \in \mathbb{N} , 7\mid(2^n-1) \iff 3\mid n$

Prove that $\forall n \in \mathbb{N} , 7\mid(2^n-1) \iff 3\mid n$. The hint is to look at the table of $\Bbb Z/7\Bbb Z$ powers of $2 \bmod 7$, and to notice how they repeat. I'm not sure if I should ...
4
votes
1answer
91 views

Prove or refute: $a[n]=\lfloor(n+1)\pi\rfloor-\lfloor n\pi\rfloor$ is periodic.

Prove or refute: $a[n]=\lfloor(n+1)\pi\rfloor-\lfloor n\pi\rfloor$ is periodic. This sequence looks periodic, starting with ${3, 3, 3, 3, 3, 3, 4, \,3, 3, 3, 3, 3, 3, 4,\, 3, 3, 3, 3, 3, 3, ...
3
votes
3answers
67 views

explain why $3|n$ with the following conditions..

If $ord_ma=3$ and if $a^n\equiv 1 \pmod{m}$ for some $n\ge1$, explain why $3|n$. Attempt at solution: We know that $ord_ma=3$ means $a^3\equiv 1 \pmod{m}$. Therefore, $n$ is a multiple of $3$, ...
1
vote
2answers
81 views

If $\operatorname{ord}_ma=10$, find $\operatorname{ord}_ma^6$

If $\operatorname{ord}_ma=10$, find $\operatorname{ord}_ma^6$. Justify you're answer. I'm not sure what I should say for my answer to be justified. However, I expect $\operatorname{ord}_ma^6=5$, ...
3
votes
2answers
117 views

solutions of $a^2+b^2=c^2$

I am trying to figure the following out. If you have $a^2+b^2=c^2$ and let $x=a/c$ and $y=b/c$ how can you show that $x=\frac{m^2-n^2}{m^2+n^2}$ and $y=\frac{2mn}{m^2+n^2}$ for some relatively ...
0
votes
1answer
56 views

How many elements of $\mathbb Z_{4536}$ satisfy $4991t = 460$ in $\mathbb Z_{7429}$

Not sure if these are relevant but the previous questions asks: Find $gcd(7429, 4991)$ Worked out to be $23$ Express 4991 as product of primes: $23 * 7 * 31$ Find all integer solutions for $7429x + ...
0
votes
1answer
58 views

Finding factor with primes [closed]

If $p$ is a prime other then $2$, express the general prime factor of $2^p-1$ in terms of p and some other integer.
1
vote
1answer
125 views

Lucas' primality test == finding a primitive root?

I'm looking at some definitions of Lucas' primality test and as far as I can see the algorithm for the examples shown on most sites seem to just be "For some number $n$ if $n$ has a primitive root ...
0
votes
1answer
38 views

Is every natural number a difference between natural numbers with greatest common divisor 1.

Can one prove that $\{x : x=y-z, \gcd(y,z)=1, y,z\in \mathbb{N}\}=\mathbb{N}$? This problem has arisen at a problem in probability and I've never studied this kind of math before, so I apologize if ...
1
vote
1answer
239 views

integer solutions of an equations

Now I came with an equation to find the solutions in integers. Not aonly that, I would like to know other types of solutions (if exists). Find the solutions and method of solving the equation $p^3 - ...
1
vote
2answers
229 views

Congruence Classes and the Chinese Remainder Theorem

I am looking for some hints please! Show that if $m = p_1\cdots p_r$ is a product of distinct odd primes, the set of odd $a$ such that $\left(\dfrac{a}{m}\right) = 1$ are those lying in half of the ...
3
votes
1answer
403 views

Very elementary proof of the prime number theorem

Can someone tell me if anything is wrong with this proof? It seems too good to be true, as it was very easy to create. $$ \lim_{x \rightarrow \infty} \frac{\psi(x)}{x} =c $$ $$ ...
4
votes
4answers
331 views

Mathematical proof for long-term behavior of a sequence of integer vectors

There are some children sitting around a round table. Each child is given an even amount of $1$-cent coins ($0$ is even) by their teacher, all the children at once. A child will give half his money to ...
0
votes
3answers
988 views

Sum of three squares: need to check the expressions with the lower powers of $4$.

It is a well-known theorem that a positive integer cannot be expressed as a sum of three squares iff. it is of the form $4^n(8m+7)$ for some non-negative integers $m$ and $n$. E.g. ...
1
vote
0answers
54 views

Inequality help

Can someone help me prove the inequality, $$ \frac{\sum\limits_{k=1}^n \Lambda(k) \frac{k}{n}\lceil\frac{n}{k}\rceil\{ \frac{n}{k} \}}{\sum\limits_{k=1}^n \Lambda(k)}<\ \frac{\sum\limits_{k=1}^n ...
3
votes
1answer
130 views

Let $a_n = n^n$. For all $n \in \Bbb N$, show that

Let $a_n = n^n$. For all $n \in \Bbb N$, show that There exists some $k \in \Bbb N$ such that for each $n \in \Bbb N$ we have: $a_{n+k} \equiv a_n \pmod m$ where $m \gt 1$ is a square-free integer. ...
3
votes
0answers
109 views

Limit involving sums of the Von-Mangoldt function

Can someone show that the limit bellow approaches 1/2? Can you also prove that it does, with out using the prime number theorem? $$ \lim_{n\to\infty} \frac{\sum\limits_{k=1}^n \Lambda(k) ...
1
vote
1answer
65 views

What can I say about $x^4 \equiv -4 \mod p$ where $p$ is prime?

What can I say about $x^4 \equiv -4 \mod p$ where $p$ is prime? In general what can I do with powers that are greater than $2$ and where I cannot use reciprocity, legendre/jacobi etc... In general ...
2
votes
2answers
338 views

Order of numbers modulo $p^2$

Let $p$ be an odd prime and let $g$ be a primitive root modulo $p$. Prove that either $\,p+g\,$ or $\,g\,$ has order $\,p^2-p\,\pmod{p^2}$. Remark: We know $\,g^{\frac{p-1}{2}}=-1\,$.
4
votes
0answers
117 views

Show that if we have a product of distinct odd primes m, then they lie in half of b modulo m.

I'm having a lot of difficultly understanding the approach I should use for this problem. I was wondering if anyone would be able to provide some assistance. Show that if m = p1....pr is a product of ...
1
vote
1answer
371 views

Multiplication Table with a frame and picture of equal sum

Is there an $n \times n$ multiplication table such that if you form a border of width $k$ ("the frame") and sum its elements, the total will equal the sum of the remaining elements ("the picture")? ...
1
vote
2answers
199 views

Modular arithmetic, congruence classes and the jacobi symbol

Find a modulus $m$ and a finite list of congruence classes $a_1, ..., a_r \mod m$ such that $(\frac{7}{n}) = 1 \iff n \equiv a_i \mod m$ for some $i = 1$ to $r$. Let me know if I am on the right ...
3
votes
1answer
219 views

Help on proving that every natural number co-prime with 10 is a factor of a repunit [duplicate]

Possible Duplicate: Proof that a natural number multiplied by some integer results in a number with only one and zero as digits Why (directly!) does every number divide 9, 99, 999, … or 10, ...
1
vote
3answers
685 views

number of trailing zeros in a factorial in base ‘b’

I know the formula to calculate this, but I don't understand the reasoning behind it: For example, the number of trailing zeros in $100!$ in base $16$: $16=2^4$, We have: ...
1
vote
2answers
87 views

Bounds on difference of squares representations of integers [duplicate]

Possible Duplicate: $a^2-b^2 = x$ where $a,b,x$ are natural numbers I'm trying to find all the $(m,n)$ pairs that satisfy $m^2-n^2=r$, where $r$ is a given positive odd integer, ...
9
votes
3answers
241 views

Half the rationals?

Let $\mathbb{Q}[n]$ be the set of rational numbers with denominator $\le n$ and for any $X\subseteq \mathbb{Q}$, let $X[n]=X\cap \mathbb{Q}[n]$. Is there a set of rational numbers, X, such that for ...
3
votes
1answer
335 views

Infinitely many primes for quadratic residues

Let $a \in \mathbb{N}.$ Prove there are infinitely many primes $p$ satisfies $$\left(\frac{a}{p}\right) =1$$. Remark: One may need to use the Dirichlet theorem, which states that if $a,m$ are ...
6
votes
3answers
417 views

The positive integer solutions for $2^a+3^b=5^c$

What are the positive integer solutions to the equation $$2^a + 3^b = 5^c$$ Of course $(1,\space 1, \space 1)$ is a solution.
6
votes
2answers
142 views

Smallest value of $(a+b)$

What can be the smallest value of $(a+b)$ , $a>0$ and $b>0$ where $(a+13b)$ is divisible by $11$ and $(a+11b)$ is divisible by $13$ This is what I have done so far. We have 1) $a+ 13b = ...
3
votes
4answers
206 views

Using induction to prove $3$ divides $\left \lfloor\left(\frac {7+\sqrt {37}}{2}\right)^n \right\rfloor$

How can I use induction to prove that $$\left \lfloor\left(\cfrac {7+\sqrt {37}}{2}\right)^n \right\rfloor$$ is divisible by $3$ for every natural number $n$?
3
votes
5answers
189 views

Congruence modulo p

Let $p$ be an odd prime and let $1\leq n<p-1.$ Show that $$\sum_{t=1}^{p}t^n \equiv 0 \pmod{p}$$ Remark: It seems one can not apply Fermat's little theorem directly as $n<p-1$
2
votes
3answers
298 views

Primitive root modulo p

Let $p$ be an odd prime with a primitive root $g$. Prove that $$\prod_{x=1}^{\frac{p-1}{2}}x^2 \equiv (-1)^{\frac{p+1}{2}}\pmod{p}.$$ Remark: I intend to use the relationship $g^{\frac{p-1}{2}} ...
3
votes
1answer
125 views

Bounds for the size of a circle with a fixed number of integer points

I know that there are infinitely many rational points on the (unit) circle. I am interested in the following question: How large has the radius of a circle to be, such that there are at least $n$ ...
0
votes
1answer
80 views

primes, patterns, recognizable

The pairs $6h-1$ and $6h+1$ are not twin primes, that is at least one of them is factorizable/decomposable, where $h$ can be found from any of the following equations: $$ \begin{align} h = 6t_1t_2 ...