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

learn more… | top users | synonyms (1)

2
votes
0answers
56 views

Which assignment defines a bijection here? And what is its inverse? And why?

In order to make an argument given in A First Course in Modular Forms by Diamond-Shurman to count the cusps of $Γ_0 (N)$ in the context of modular curves more rigorous, I want to prove that there is a ...
3
votes
2answers
149 views

Find all answers of $n^2-2^m=1$

Find all natural numbers $(n,m)$ where $n^{2}-2^{m}=1$. I have my own answer of that, however I wanted to know if anyone has a better or easier answer or not!
1
vote
3answers
35 views

Why is the set over which we one takes the max for gcd(a, b) is a subset of the set for gcd(a, b − a)?

In my book, the definition for gcd(a,b) is the following: $$\gcd (a,b) = \max \{ d \in \Bbb{Z} : d|a \, \land \, d|b \}$$ However, I don't understand why the set for $\gcd(a,b)$ is necessarily a ...
17
votes
4answers
489 views

Do there exist infinitely many pairs of primes $(p,q)$ such that $pq$ divides $2^{p-1}+2^{q-1}-2$?

A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:- Do there exist infinitely many pairs of primes $(p,q)$ such that ...
5
votes
2answers
293 views

Can both $x^2 + y+2$ and $y^2+4x$ be squares?

Prove that there exist no positive integers $x$ and $y$ such that both $x^2+y+2$ and $y^2+4x$ are perfect squares. I thought I could perhaps solve this by square bounding but I couldn't get anywhere ...
13
votes
1answer
557 views

Can the order of 2 mod p be arbitrarily small (relative to $p - 1$)?

Given a prime number $p$, let $\operatorname{ord}_p(2)$ be the multiplicative order of $2$ modulo $p$, i.e., the smallest integer $k$ such that $p$ divides $2^k - 1$. By Lagrange's theorem, ...
8
votes
3answers
267 views

Number theory: Prime powers and cubes

Determine all triples $(p,a,b)$ of positive integers, where $p$ is prime and $a \leq b$ such that $$p^a+p^b$$ is a perfect cube. I came across this question while looking at past maths Olympiad ...
3
votes
1answer
52 views

Express in terms of familiar arithmetic functions

How can I express the sumation $$h_k(n)=\sum_{d|n, k|d}\mu (d)$$ in terms of familiar arithmetic functions, where $k\in \mathbb{N} $ is fixed?
4
votes
2answers
708 views

Proof for gcd associative property:

I'm trying to prove\show the associative property for the $\gcd(a,b)$ function. $$\gcd( a ,\space \gcd(b,c) ) = \gcd(\space \gcd(a,b) , c )$$ Let: $$e = \gcd( a ,\space \gcd(b,c) )\text{ and }f = ...
21
votes
2answers
495 views

A question on elementary number theory

Just came across the following question: Let $S=\{2,5,13\}$. Notice that $S$ satisfies the following property: for any $a,b \in S$ and $a \neq b$, $ab-1$ is a perfect square. Show that for any ...
6
votes
2answers
112 views

If a prime $p$ satisfies $p \equiv 5 \mod 12$, then $p \in \mathbb{Z}(\sqrt{3})$ is irreducible.

I would like to show that if a prime $p$ satisfies $p \equiv 5 \mod 12$, then $p \in \mathbb{Z}(\sqrt{3})$ is irreducible. The following fact, which I have proven, seems to be helpful: Let $N$ ...
2
votes
2answers
118 views

Can you prove if $5^n \mid r$ and $r$ odd then $5^{n+1} \mid 2^r+3^r$?

I've looked around at this, but been unable to find it. After generating prime factorizations in Maple of $2^r+3^r$ for $r>0$ it seems that this holds. It's easy enough to prove case by case. The ...
16
votes
6answers
1k views

Prove $a+b+c+d $ is composite

Let $a,b,c,d$ be natural numbers with $ab=cd$. Prove that $a+b+c+d$ is composite. I have my own solution for this (As posted) and i want to see if there is any other good proofs.
1
vote
2answers
61 views

Finding the kth term of an iterated sequence

The sequence $x_0, x_1, \dots$ is defined through $x_0 =3, x_1 = 18$ and $x_{n+2} = 6x_{n+1}-9x_n$ for $n=0,1,2,\dots\;$. What is the smallest $k$ such that $x_k$ is divisible by $2013$?
3
votes
1answer
202 views

Average of divisors of n.

Let n be a natural number and let $f(n)=\frac{\sigma(n)}{d(n)}$ be the arithmetical average of n's divisors. Either prove or give a counterexample that for all natural numbers like n, which are not ...
-3
votes
2answers
192 views

I need help with the proof of Theorem 4, Chapter I in E. Landau's “Foundations of Analysis”

I need help with the proof of Theorem 4, Chapter I in E. Landau's "Foundations of Analysis" To every pair of natural numbers $x$, $y$, we may assign in exactly one way a natural number, called ...
3
votes
2answers
687 views

Prove by mathematical induction for any prime number$ p > 3, p^2 - 1$ is divisible by $3$?

Prove by mathematical induction for any prime number $p > 3, p^2 - 1$ is divisible by $3$? Actually the above expression is divisible by $3,4,6,8,12$ and $24$. I have proved the divisibility by ...
4
votes
0answers
124 views

Generalizing Ramanujan's 6-10-8 Identity

Let $ad=bc$. Then Ramanujan's 6-10-8 Identity is the bizarre, $$64[(a+b+c)^6+(b+c+d)^6-(c+d+a)^6-(d+a+b)^6+(a-d)^6-(b-c)^6][(a+b+c)^{10}+(b+c+d)^{10}-(c+d+a)^{10}-(d+a+b)^{10}+(a-d)^{10}-(b-c)^{10}] ...
5
votes
1answer
98 views

Constraints on $x$ such that $2x+1$ is prime

I have read quite a bit about prime numbers recently (having just started a module on elementary number theory, groups, primes, etc.), and something that always seems to be popping up is powers of 2. ...
31
votes
6answers
6k views

Are all prime numbers finite?

If we answer false, then there must be an infinite prime number. But infinity is not a number and we have a contradiction. If we answer true, then there must be a greatest prime number. But Euclid ...
1
vote
0answers
203 views

Fourier Analysis of Prime Counting Function

I was thinking about the following: Denote $\pi(x)$ as the prime counting function such that: $$ \pi(x) = \#\text{ of prime numbers}\leq x $$ It is well known from the prime number theorem that $$ ...
7
votes
1answer
61 views

Solution of $x^3+x^2-12x=0$ in $\mathbb{Z}_{11}$

I am trying to solve $x^3+x^2-12x=0$ in $\mathbb Z_{11}$. I find $3$ solutions: $0, 3$ and $7$ but the book claims that there are only $2$ solutions. Am i doing something wrong? Thank you
1
vote
1answer
203 views

Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number

Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number. If true (which I'm pretty sure it isn't), then the proof needs to be in either contradiction or ...
1
vote
5answers
465 views

Prove that if $a, b, c$ are positive odd integers, then $b^2 - 4ac$ cannot be a perfect square.

Prove that if $a, b, c$ are positive odd integers, then $b^2 - 4ac$ cannot be a perfect square. What I have done: This has to either be done with contradiction or contraposition, I was thinking ...
3
votes
2answers
301 views

How many solutions are there to $abc+def=ghi$, where $a,b,\ldots, h,i$ are distinct non-zero digits?

I saw this problem posted by Google. Those posting in the comments found solutions using computer programming. I would like to know if there is an easier solution than trying every single combination. ...
3
votes
1answer
87 views

Factorization of the trinomial $x^{2n}+Dx^n+1$?

The following trinomials will factor for any $a$, $$1+a(-3+a^2)x^3+x^6 = (1+ax+x^2)(1-ax-x^2+a^2x^2-ax^3+x^4)\tag{1}$$ and similarly for, $$1+a(5-5a^2+a^4)x^5+x^{10}\tag{2}$$ ...
4
votes
1answer
91 views

A combinatorial number theory question (pigeonhole principle)

Let $n$ be a positive integer such that $n$ and $10$ are coprime. Prove that $n|11\cdots11$ for some $11\cdots11$ in base 10 representation. This problem is about pigeonhole principle, I have a great ...
1
vote
2answers
60 views

Numbers of the form $abc,abc$

Can you please provide hints? A 6 digit number can be written by repeating a three digit number, such as 359, 359. What is the greatest integer which divides any such 6 digit number? I can see that ...
5
votes
1answer
493 views

Find all integer solutions to $x^2+4=y^3$. [duplicate]

Find all integer solutions to $x^2+4=y^3$. Some obvious solutions are $(x,y)=(\pm2,2)$. Are these the only ones?
1
vote
1answer
93 views

Simple Number Theory Identity Regarding Subtraction

Take these two digit numbers: $$xa$$ $$yb$$ Assume $$x>y>0$$ and $$b>a>=0$$ and we are to subtract the two numbers. If for example we set, a=3 and b=6, the unit digit of this subtraction ...
1
vote
1answer
174 views

How quickly can we detect if a digit is in a number?

If we suppose that we have a number $n$ in base $b$, represented as a power series: $$n = d_0 b^0 + d_1 b^1 + d_2 b^2 + \dots$$ ...where the $d_k$'s are the digits, how quickly can we determine if ...
0
votes
1answer
103 views

How can I solve this really easy number theory/modular arithmetic problem in Maple?

Math people: This is more of a Maple question than a math question, but I think I will get an answer more quickly here than at mapleprimes.com. I spent a lot of time on Google, mapleprimes.com, and ...
1
vote
1answer
33 views

Proving $n\equiv p [k] \Longleftrightarrow \gcd(p,k)=\gcd(n,k)$

I'm wondering if this statement is correct : $n\equiv p [k] \Longleftrightarrow \gcd(p,k)=\gcd(n,k)$. If it is: What are the conditions that must be assured before using it? How can I prove that ...
4
votes
1answer
98 views

how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $

how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $
2
votes
1answer
148 views

complete residue system modulo $p$

if $p$ is odd prime and $\{a_1,...,a_p\},\{b_1,...,b_p\}$ are complete residue system modulo $p$ how to prove $\{a_1b_1,...,a_pb_p\}$ is not complete residue system modulo $p$. complete residue ...
7
votes
2answers
242 views

Solve: $x^2-py^2=q$

Solve $$x^2-py^2=q$$ for integers $x,y$, here $p,q$ are both given prime numbers. It's obvious that $p,q$ should satisfy $(\frac{p}{q})=(\frac{q}{p})=1,$ here $(\frac{p}{q})$ is the Jacobi symbol. ...
3
votes
3answers
105 views

If $t_1\mid p-1$ and $t_2\mid q-1$, then $\text{lcm}(t_1,t_2) \leq \text{lcm}(p-1,q-1)$

Let $p,q $ be primes. It is given that $t_1$ divides $p-1$ and that $t_2$ divides $q-1$. Can it then be proved that $\text{lcm}(t_1,t_2) \leq \text{lcm}(p-1,q-1)$
6
votes
1answer
412 views

Generalizing Ramanujan's sum of cubes identity?

Ramanujan's sum of cubes identity is defined by the generating functions, $$\begin{aligned} \sum_{n=0}^\infty a_n x^n &= \frac{1+53x+9x^2}{R_1}\\ \sum_{n=0}^\infty b_n x^n &= ...
1
vote
2answers
141 views

Are the propreties of arithmetic unproven?

For example, the property which says that $$a(b+c)=ab+ac$$ This is very clear for integers, but is it actually provable for all real numbers (and complex maybe). Or the commutative property which says ...
1
vote
4answers
117 views

Is there something faulty about this statement?

Show any prime of the form $3k+1$ is of the form $6k+1$. I came up with my own solution that made perfect sense to me, but when I read the text's solution, it argued that for the primes that are of ...
5
votes
2answers
216 views

Proving the congruence $p^{q-1}+q^{p-1} \equiv 1 \pmod{pq}$

If $p$ and $q$ are distinct primes , prove that $$p^{q-1}+q^{p-1} \equiv 1 \pmod {pq}$$ Using Fermat's Theorem we can get $$p^{q-1} \equiv 1 \pmod q, \qquad q^{p-1} \equiv 1 \pmod p.$$ After ...
8
votes
2answers
86 views

Are the high-order bits of $n^2$ as likely to be zeroes as ones?

Let $B_i(n)$ be the $i$th bit in the binary expansion of $n$, so that $n=\sum B_i(n)2^i$. Now let $n$ be randomly and uniformly chosen from some large range, and let $E(j)$ be the expected value of ...
2
votes
1answer
432 views

Computing $\bmod$s with large exponents by paper and pencil using Fermat's Little Theorem.

I'm having a bit of trouble computing $\bmod{mod}$s of large numbers using Fermat's Little Theorem. For example, how would you compute $7^{435627650}\mod 13$? The solution given is $435627650\mod ...
2
votes
1answer
267 views

Computing RSA Algorithm

Modulus $N=247$; encryption exponent $r=7$ Encrypt $100$; Decrypt $120$. $Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$. For a discrete math ...
0
votes
1answer
56 views

Question regarding Legendre symbol and Quadratic reciprocity.

How would determine the value of the following Legendre symbol is $1$ or $-1$? $$\left(\frac{\frac{p - 1}{2}}{p}\right)$$ So far, I've been able to figure out this much: $$\left(\frac{p - ...
1
vote
1answer
80 views

Looking for name of theorem: “rational $\Leftrightarrow$ fractional part terminates or repeats”

I am looking for the name of the theorem that says that a number $x$ is rational if and only if its fractional part terminates or repeats (where "fractional part" refers to the representation of $x$ ...
3
votes
4answers
86 views

Solving for Modular arithmetic

Solve the equation $38z\equiv 21 \pmod {71}$ for z. Little confused by the questions. My attempt is: $38 \odot z = 21.$ Then find the inverse of 38 from mod 71 and multiply both sides. Lastly, take ...
3
votes
2answers
54 views

Does there exist an integer $x$ satisfying the following congruences?

Does there exist an integer $x$ satisfying the following congruences? $$10x = 1 \pmod {21} \\ 5x = 2 \pmod 6 \\ 4x = 1 \pmod 7$$ I was trying to do this by following way but failed to get an ...
2
votes
5answers
88 views

If $p$ be a prime and r be any integer, $0 < r < p$ then $\frac{(p-1)!}{r!(p-r)!}$ is an integer.

Let $p$ be a prime and r an integer, $0 < r < p$. Show that $\frac{(p-1)!}{r!(p-r)!}$ is an integer. The given number is $ \frac{\binom {p} {r}}{p}$. after tha how can I show that$p$ divides ...
7
votes
2answers
192 views

Does there always exist an odd number of elements?

Given a nonzero integer $k$, does there always exist a positive integer $n$ such that there are exactly an odd number of elements $i\in\{0,1,...,n-1\}$ with $\frac{2^n-1}4 < 2^ik \mod{2^n-1} < ...