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

learn more… | top users | synonyms (1)

4
votes
1answer
165 views

Show that if $n$ is is a positive integer such that $n\ne 2$ and $n\ne 6$ then $\phi(n) \ge \sqrt n$

$\phi(n)$ being Euler's totient function. Regarding effort put into the problem: In the case that $n$ is a prime $p$, then it is given that $\phi(p) = p-1$. It is also given that $n\ne 2$, so the ...
2
votes
2answers
94 views

Does $7$ divide $2 x^2 - 4y^2$ for all $x,y$?

Does $7$ divide $2 x^2 - 4y^2$ for all $x,y \in \mathbb{Z}$?
2
votes
1answer
158 views

About the multiplicative order of $2$ modulo a prime

Is this true, that for all integer $n>0$, but $n=1$ and $n=6$, there exists a prime $p$ such that $n=ord_p(2)$, where $ord_p(2)$ is the multiplicative order of $2$ modulo $p$? If not, what is the ...
5
votes
1answer
69 views

How to prove that all primes $p$ will have a power $p^k$ with a $2$ in its decimal representation?

How to prove that all primes $p$ will have a power $p^k$ with a $2$ in its decimal representation? This is a lemma I need to prove a problem I'm working on. My attempt: Suppose for the sake of ...
5
votes
2answers
171 views

Finding the summation of the floor of the series identity

I would appreciate if somebody could help me with the following problem: Q: How to proof ? The number of positive divisors of $n$ is denoted by $d(n)$ ...
7
votes
2answers
219 views

Prove that $n^7+7$ can never be a perfect square.

Prove that for a positive integer $n$, $n^7+7$ cannot be a perfect square. I managed to show that $n \equiv 5 \pmod{8}$ or $n \equiv 9 \pmod{16}$. But nothing came from that so I presume another ...
2
votes
1answer
510 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
6
votes
0answers
47 views

Inverse image of rationals under tangent function is free abelian?

It is easy to see that the set $\{x:\tan x\in \Bbb Q \,\, or\,\, \pm\infty\}$ forms a group under addition. It is a free abelian group?
4
votes
1answer
102 views

Question about the number of primes greater than $3$ in a sequence of consecutive integers.

I recently noticed that for any $x > 16$, it follows that there are at least $2$ integers in the any sequence of 3 consecutive integers that are divisible by a prime greater than $3$. For example, ...
6
votes
1answer
297 views

Elementary proof of prime number theorem?

From Wikipedia: "The prime number theorem is also equivalent to: $$lim_{x \rightarrow \infty} \frac{\psi(x)}{x}=1$$ where $$\psi(x) = \sum\limits_{n \leq x} \Lambda(n)$$ is the Chebyshev function. ...
3
votes
1answer
85 views

Failing Fermat Primality Test

Consider the following algorithm: Suppose $n\geq 2$, and let FermatTest be an algorithm such that if $a^{n-1}\not\equiv 1\mod n$ then return composite. If FermatTest yields $a^{n-1}\equiv 1 \mod n$, ...
0
votes
2answers
221 views

Show that if $\gcd(a,b)=1$ and $p$ is an odd prime, then [duplicate]

Show that if $\gcd(a,b)=1$ and $p$ is an odd prime, then ${\gcd(a+b,}\frac{a^p +b^p}{a+b}$$) = 1$ or $p$ Sorry about the duplicate In another answer, however, the sum $\sum\limits_{k=0}^{n-1} ...
0
votes
1answer
74 views

Prove that $\mu(a, b)= \mu(1, b/a)$.

Let $n$ be a positive integer and consider the partially ordered set $(X_n, \;|\; )$, where $X_n = \{1, 2, ... ,n\}$ and the partial order is that of divisibility. Let a and b be positive integers in ...
1
vote
2answers
133 views

Newton's Method for estimating square roots.

Sometime ago I wrote a program that used Newtons Method and derivatives to approximate unknown square roots (say $\sqrt 5$) from known square roots like $\sqrt 4$.I have since lost the calculator and ...
1
vote
1answer
106 views

The first odd multiple of a number in a given range

As a part of a programming problem I was solving, we were required to find the first offset of a range at which the number is a odd multiple of another number. For e.g: Take the range $100$ to $120$. ...
2
votes
2answers
102 views

Divisible by what?

$1^n+2^n+\ldots+2006^n$ is divisible by : $1.~2006$ $2.~2007$ $3.~2008$ $4.~\text{None}$ Please Explain.
2
votes
0answers
511 views

The set of all natural numbers is closed under addition

I'm trying to prove the theorem described in the title, but my proof is so obvious I doubt it is sufficient. Here's my way of proving it: Definition of addition: Let a, b, and c be natural numbers. ...
1
vote
2answers
96 views

Easy linear combinations problem.

A small gear with 17 teeth is meshed into a large gear with 60 teeth. The large gear starts rotating at one revolution per minute. How long will it take until the small gear is back to its original ...
0
votes
2answers
81 views

What is $25^4 mod 39$ congruent to?

My result is $25^4 \equiv 25 (\textrm{mod}\ 39)$, but Wolfram Alpha simplifies $25^4 \ \textrm{mod}\ 39$ as 1. How should I interpret this? I have the following ...
1
vote
0answers
41 views

Congruence equations

Given positive integer $Z, N$ and a set of positive integer $S$. Find smallest $k \in \mathbb{Z^+}$ such that $$a*k +1 \equiv Z \pmod N \ a\text{ is a positive integer that we don't know, and}\\ i*k ...
1
vote
2answers
56 views

Prove that $x^2 \equiv a \bmod{p}$ has a solution for exactly half of the integers of $a$ satisfying $1 \le a \le p - 1$.

Let $p$ be an odd prime. I want to prove that $x^2 \equiv a \bmod{p}$ has a solution for exactly half of the integers of $a$ satisfying $1 \le a \le p - 1$. Am I supposed to use $\gcd(2, p - 1)$ for ...
7
votes
3answers
627 views

If a prime can be expressed as sum of square of two integers, then prove that the representation is unique.

If a prime can be expressed as sum of two squares, then prove that the representation is unique. My attempt: If $a^2+b^2=p$, then it is obvious that $a,b$ of different parity. Now, I assume the ...
17
votes
6answers
2k views

Visual explanation of the following statement:

Can somebody fill me in on a visual explanation for the following: If there exist integers $x, y$ such that $x^2 + y^2 = c$, then there also exist integers $w, z$ such that $w^2 + z^2 = 2c$ I know ...
-1
votes
1answer
24 views

Turn formula with remainder

How do I turn these formulas: $$\begin{align} y &= \left\lfloor\frac{ x \mod 790}{10}\right\rfloor + 48 \\ z &= (x \mod 790) \mod 10 + 10\left\lfloor\frac{x}{790}\right\rfloor + 48 ...
0
votes
1answer
42 views

I want to prove that if $n$ is composite and $\varphi(n) \mid (n - 1)$, then $n$ is squarefree

I want to prove that if $n$ is composite and $\varphi(n) \mid (n - 1)$, then $n$ is squarefree. To show that $n$ is squarefree in my problem, I want to show there is no prime $p$ such that $p^2 \mid ...
3
votes
3answers
178 views

Prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$.

I want to prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$. It's given that $d \mid n$, so we know that $n = dm$, for some $m \in \mathbb{Z}$. Now, I want to show that ...
3
votes
3answers
75 views

Solving for $3^x - 1 = 2^y$

Besides $x=2, y=3$, are there any other solutions? I know that if there is another solution: $y$ is odd since $2^y \equiv -1 \pmod 3$ $x$ is even since $3^x - 1 \equiv 0 \pmod 8$ $3 | y$ since $-1 ...
1
vote
0answers
51 views

Prove that for every prime $p > 100$ and every integer $r$ $\exists a, b$ such that $p \mid a^2 + b^5 - r$

Prove that for every prime $p > 100$ and every integer $r$ $\exists a, b \in \mathbb{Z}$ such that $p \mid a^2 + b^5 - r$ Preferably without using Jacobi sums, I have already seen a solution using ...
1
vote
2answers
87 views

Let $r$ be the smallest positive integer such that $a^r \equiv 1 \bmod{n}$. Prove $r \mid \phi(n)$.

Let $a \in \mathbb {Z}$, $n > 1$ a natural number with $\gcd(a, n) = 1$, and let $r$ be the smallest positive integer such that $a^r \equiv 1 \bmod{n}$. Prove that $r \mid \phi(n)$. Euler's ...
4
votes
1answer
309 views

Prove that if $m$, $n$ $\in \mathbb {N}$ with $g=\gcd(m, n)$, then $\phi(mn) = \frac{g\phi(m)\phi(n)}{\phi(g)}$

I want to solve the following problem: Prove that if $m$, $n$ $\in \mathbb {N}$ with $g=\gcd(m, n)$, then $$\phi(mn) = \frac{g\phi(m)\phi(n)}{\phi(g)}$$ I know I want to use the multiplicative ...
3
votes
4answers
55 views

Number of triplets adding to a certain number

Suppose I have $L$ and $m$ in $\mathbb{N}$. What is the cardinality of the set $$ \{ (x_1, x_2, x_3) \in \mathbb{N}^3 : x_1 + x_2 + x_3 = L, x_i > m \}? $$ An exact number would be great but I ...
0
votes
1answer
101 views

Proof by induction of the value of $3^n$ modulo 10

I am learning proof by induction in my math class and I am having trouble with this problem: Prove that for $k \in N, 3^{4k-3}\equiv 3 \pmod{10}, 3^{4k-2} \equiv 9 \pmod{10}, 3^{4k-1} \equiv 7 ...
3
votes
3answers
65 views

Let $p$ be prime. Does $x^3 \equiv a\bmod{p}$ have a solution for every $a$?

Let $p$ be prime. Does $x^3 \equiv a\bmod{p}$ have a solution for every $a$? Here is my first idea: I know that $$x^3 \equiv a\bmod{p}$$ iff $$p\mid x^3-a$$ iff $$x^3-a=pm$$ Where $m \in ...
5
votes
2answers
77 views

If $1 \sim 2$ and $2 \sim 3$, how is $\sim$ an equivalence relation?

I'm asked to describe an equivalence relation on $S \in \{1,2,3,4\}$ where $1 \sim 2$ and $2 \sim 3$. However I'm a little confused over why this qualifies as an equivalence relation, since through ...
1
vote
3answers
63 views

Greatest Common Divisor property: If $\gcd(a, b) = 1$ and $a | c$ and $b | c$, then $ab | c$ [duplicate]

Here is what I am trying to prove: Let $a,b,c,d \in ℤ_+$ with gcd$(a,b)=1$. If $a|c$ and $b|c$, prove that $ab|c$. Does the result hold if gcd $(a,b)\neq 1$ ? I know that gcd $(a,b)=1$ can be ...
5
votes
4answers
66 views

Greatest common divisor of two relatively primes

Here is the question I am trying to prove: If $a,b$ are relatively prime and $a>b$ prove that $\gcd(a-b, a+b) \in \{1, 2\}$. Can I begin with something like $(a-b)k + (a+b)l = d$ where $k,l$ ...
4
votes
3answers
304 views

Finding a primitive root

I'm trying to find a small primitive root modulo $p^k$, where $p$ is prime. My strategy is to test small numbers $g=2,3,\ldots$ until I find a primitive root modulo $p$. That is, until ...
1
vote
4answers
136 views

Prove that if $n$ is composite, then $(n-1)! \equiv 0 \pmod n$ [duplicate]

This theorem is the converse of Wilson's theorem: If $n$ is composite and $n>4$, then $(n-1)! \equiv 0 \pmod n$ The question holds up for all the composites I have tried but I'm struggling to ...
1
vote
0answers
54 views

$\left\lfloor(\sqrt[3]{28}-3)^{-n}\right\rfloor$ is not divisible by 6 [duplicate]

let $n$ be a positive integer. Prove that the following expression: $$\left\lfloor(\sqrt[3]{28}-3)^{-n}\right\rfloor$$ is not divisible by 6. $\lfloor x\rfloor$ is the greatest integer less than or ...
2
votes
1answer
80 views

A problem on Möbius function

Here is an exercise from the text book "Combinatorics" (J.H.van Lint, R.M. Wilson) Let $f_n(z)$ be the function that has all its zeros as all the numbers $\alpha$ for which $\alpha^n=1$ but ...
2
votes
4answers
95 views

Safe prime mod 24

Given a safe-prime $p = 2q + 1$ where $q$ is also a prime and $p \gt 7$, I've read in a crypto.se answer that either $p \equiv 11 \pmod {24}$ or $p \equiv 23 \pmod {24}$. I understand the proofs of ...
0
votes
2answers
68 views

trying to teach negative times negative number positive answer

I am thinking of negative times negative numbers as: $$-3 \cdot 2 = (-2) + (-2) + (-2) = -6$$ $$2 \cdot -3 = (-3) + (-3) = -6$$ $$-3 \cdot -2 = (-(-2)) + (-(-2)) + (-(-2)) = 6$$ I am trying ...
1
vote
1answer
131 views

RSA Ciphertext Message.

Hey I'm really stuck and I have to finish soon. Part A Ray, Sam and Todd are lazy, and they have set up their RSA public keys as $(3,nR),(3,nS),(3,nT)$ respectively. We may assume that any two of ...
0
votes
1answer
27 views

Separate these into as many equations as possible using Chinese Remainder Theorem

$x = 45 \mod 18$ $x = c^d \mod n^2m$ for gcd$(n,m) = 1$ I'm not really sure how we can tell how many equations it's possible to split these into. Moreover, I'm not even sure how to split them into ...
2
votes
3answers
130 views

what is the remainder if we divide $72^{200}$ by $5$?

What is the remainder if we divide $72^{200}$ by $5$? I am very new to modular arithmetic! Please help!
1
vote
0answers
69 views

Irrational numbers and series

Let $$f(x) = \prod_{n = 0}^\infty \left(1 + \frac{x}{2^n}\right)$$ According to an exercise in a packet of problems in elementary number theory, this function and all its derivatives are irrational ...
1
vote
1answer
193 views

Chinese remainder theorem to solve simultaneous equations

Use the CRT to give all solutions to: $$x = 1 \mod 9$$ $$x = 3 \mod 8$$ $$3x = 5 \mod 17$$ Can the standard CRT be used to solve: $$2x^2 = 5 \mod 9$$ $$x = 13 \mod 21$$ $$2x^2 = 2 \mod 56$$ I'm ...
0
votes
3answers
42 views

easy inequality to prove

Prove that $\log_2(x)+\frac{1-x}{x} > 0$ I think the answer is easy but I've no clue how to go about it.
0
votes
1answer
28 views

Find a generator of $Z_{27}^*$

I know a generator $g \in Z_{27}^*$ means that the order of $g$ is $26$, but I'm having trouble finding an efficient method to find a generator given that the number of possibilities are very large ...
0
votes
2answers
80 views

Primality of $2^q\pm2^{(q+1)/2}+1$ when $q$ is an odd integer

It can be quite easily shown that $5$ is a divisor of $2^q+2^{(q+1)/2}+1$ iff ($q=8k+1$ or $q=8k+7$) and that $5$ is a divisor of $2^q-2^{(q+1)/2}+1$ iff ($q=8k+3$ or $q=8k+5$). Now, it seems that ...