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

learn more… | top users | synonyms (1)

1
vote
1answer
77 views

Mistake in this number theory book

I'm studying quadratic residues in this book, and I think this theorem is not stated correctly: I think the author really means $(a,p)=1$, I don't know where he uses $(a,2p)=1$ in the proof. ...
0
votes
1answer
30 views

Why $p$ disappears in this equation

I'm trying to understand why $p$ disappears in this proof from this book: Knowing the $r_i$ are the residues that exceed $p/2$ and $s_j$ the remaining residues: I really need help. Thanks in ...
0
votes
2answers
63 views

Proving a composite number is product of primes for a set

Let $A=\{4n+1:n\in\mathbb{N}\}=\{1,5,9,13,17,\dots\}$. We call a number $\alpha $ $\text{A-prime}$ if it doesn't have any divisors in $A$ aside from $1$ and $\alpha$, we define ...
0
votes
3answers
106 views

Efficient way to count perfect square multiples of $24$ less than $10^6$

How many positive perfect square less than ${10^6}$ are multiples of 24. I know you can list all the multiples of 24, and compute the square of each of them as you increase the number by 24. But what ...
2
votes
3answers
104 views

Intuition - Linear Congruence Theorem

Let a and b be integers (not both 0) with greatest common divisor d. Then an integer $c = ax + by$ for some $x, y \in Z$ $\iff d|c$. In particular, d is the least positive integer of the ...
3
votes
2answers
82 views

Ground Plan - Prove Fermat-Euclid's Totient Theorem with Lagrange's Theorem

If $\gcd(a,n) = 1$, then $a^{\phi(n)}\equiv 1\pmod n$. Here's a three-step proof. An integer a is invertible means there's some $a^{-1}$ such that $aa^{-1}\equiv 1 \pmod n$. By cause of Jones p84 ...
4
votes
2answers
276 views

Fermat's Little Theorem fails for composite instead of prime numbers.

I know Fermat's Little Theorem = Fermat-Euler's Totient Theorem when $n$ is prime. Elementary Number Theory, Jones, p83 writes if we simply replace p with a composite integer n, then the ...
1
vote
1answer
85 views

Backward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p) $.

(1) How can you preconceive to prove by contradiction? Prove by contradiction. Suppose $n$ is composite. This means there exists a divisor $d|n$ such that $1<d<n$. We are given that ...
0
votes
2answers
72 views

Ground Plan – Forward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p) $.

Lemma 5.3 - I omit proof here - Let p be prime. Then $x^2 \equiv 1 \, (mod p) \iff x \equiv \pm 1 \; (mod p)$ First we establish the result for the first two primes 2, 3. Then prove the result for ...
0
votes
1answer
69 views

finding all primes $p$ for which a given number is a quadratic residue

I have seen an exercise on the Apostol, but I haven't understood some passages. I would be very grateful if you could solve my doubts. The problem is Find all primes $p$ for which 3 is a ...
1
vote
1answer
139 views

Combining results with Chinese remainder theorem - general case

suppose we have a congruence $$ ax^2+bx+c\equiv 0 \mod (p_1\cdot p_2) $$ being $p_1$ and $p_2$ primes - actually it should be possible to extend these considerations to an arbitrary number of primes ...
2
votes
2answers
93 views

Formula for the number of solutions of the congruence equation $xy-wz=0$ over $\mathbb{Z}_p$?

The equation $xy-wz=0$ has 10 solutions over $\mathbb{Z}_2$ and 33 solutions over $\mathbb{Z}_3$ (e.g. $x=y=2 \land w=z=1$ is one of the solutions). Is there any formula for the number of solutions ...
7
votes
4answers
913 views

Bad proof that if $a + b + ab = 2020$ then $a+b=88$

Can you prove this: Let $a,b \in \mathbb{N}$. If $a + b + ab = 2020$ then $a+b=88$. This is the attempt given: $\frac{2020-88}{a b}=1$ $a+b=88$ Substituting for b using the 2nd equation. ...
9
votes
2answers
106 views

Let $a=\dfrac{3+\sqrt{5}}{2}.$ Show that $\lfloor a \lfloor an \rfloor \rfloor+n$ is divisible by $3$.

Let $a=\dfrac{3+\sqrt{5}}{2}.$ Show that for all $n\in\mathbb N$, $\lfloor a \lfloor an \rfloor \rfloor+n$ is divisible by $3$. My teacher solve this problem with induction, I am just ...
1
vote
1answer
89 views

Solution(s) for the largest remainder?

I have reached the following argument of the maximum problem: $$ \hat{x} = \mathop{\arg\,\max}\limits_x \, \rm (n\ mod\ x), \quad \text{for $1 \le x \le n$, where $x,n \in \mathbb{N}^{+}$.}$$ My ...
2
votes
1answer
27 views

The distribution on the number line of the sum of squares

If $x,y,z$ are all non-negative integers, then what is the density of $x^2+y^2+z^2$ on the number line near $N$? From the plot it seems pretty much linear, i.e. $dn/dN=C$ where $C$ is some constant ...
0
votes
3answers
51 views

Find all positive integers $n$ such that $\log_2 (n)$ is a rational number.

For $\log_2(n)$ to be a rational number, I started by stating that: $\log_2(n)=\dfrac{a}{b}$ such that $a,b \in\mathbb Z$ and $b \neq 0$ but I really don't know what step to take next?
3
votes
2answers
2k views

Why can't absolute values be expressed with negative numbers. [closed]

The answer to this question seems obvious. 'An absolute value expresses the quantity of ones between any number and 0'. But does that mean it must be positive? I took a shot at answering my ...
0
votes
4answers
104 views

Find $N$ when $N(N - 101)$ is the square of a positive integer

Let $N$ be a positive integer such that $N(N - 101)$ is the square of a positive integer. Then determine the value of $N$. OR determine all possible values of $N$. Is the fact that 101 is a prime ...
0
votes
0answers
35 views

Number theory digit sum [duplicate]

How many natural numbers less than $10^8$ are there, with sum of digits equal to $7$? My friend told me it is coefficient of $x^7$ in $\frac{(x^{10} - 1)}{(x-1)^8}$ How did he get this result? Can ...
1
vote
5answers
162 views

Last 3 digits of $3^{999}$

I know that it's $3^{999} \mod 1000$ and since $\varphi(1000) = 400$ and $3^{400}\equiv1 \mod1000$ it will be equivalent to $3^{199} \mod 1000$ but what should I do from then? Or am I wrong about this ...
2
votes
1answer
26 views

on a set of numbers with special property

Let $A$ be a set of positive Real numbers such that if $a,b \in A$ and $a\neq b$ then $a^b\in A$ or $b^a\in A$. Now prove that a finite set $A$ has no more than 4 elements. For example $A=\{1, ...
0
votes
3answers
101 views

Help in understanding proof of Möbius Inversion Formula

Help in understanding proof of Möbius Inversion Formula Could someone clarify why the equality $$\sum_{d^{'} | (n/d)} \mu(d) f(d^{'}) \sum_{d | n} \mu(d) F(n/d) = \sum_{d | n} \sum_{d^{'} | ...
2
votes
3answers
178 views

Prove that $\sqrt{7}+\sqrt{3}$ is irrational [duplicate]

Is there a method by which we can prove that $$\sqrt{3}+\sqrt{7}$$ is irrational. It's obviously an irrational number, but I want to prove that mathematically.
1
vote
1answer
41 views

Help in this proof of Legendre symbols

I need help in the second part of this theorem: I didn't understand the second part of this theorem: Why can we choose such $j$ and $j'$? What does the author mean by "the combined contribution ...
2
votes
2answers
155 views

finding a bijection from the set of Primes to the set of square-free integers

I was wondering if it is possible to construct an explicit bijection from the set of primes to the set of square-free integers. Thanks.
2
votes
1answer
47 views

In how many ways can a number be factorized over the field $\mathbb{Z}_p$ into two numbers?

For example, over the field $\mathbb{Z}_5$, we can factor number 4 into two numbers in three different ways, i.e. 4=4$\times$1, 4=2$\times$2, and 4=3$\times$3. I am looking for a general formula of ...
4
votes
0answers
91 views

How to efficiently calculate $ax+b$ once I know $a$ and $b$?

What's the cheapest way to calculate $ax+b$ several times once I know the values for $a$ and $b$? For instance, the cheapest way to calculate $ab+x$ several times once I know the values for $a$ and ...
1
vote
0answers
59 views

Determine the set of primes for which a given number is a quadratic residue

I am stuck on this topic from a while. I am looking for an algorithm to solve the following problem: Given a prime number $p$, determine the set of odd primes for which $p$ is a quadratic residue. ...
2
votes
1answer
109 views

Ground plan of Forward direction - Let $p$ be an odd prime. Prove $x^{2} \equiv -1 \; (mod \, p)$ has a solution $\iff p\equiv 1 \; (mod 4)$

Prove by contradiction. Thence suppose NOT $p\equiv 1 \; (mod 4)$. Thence 3 possibilities remain: $4|p, 4|(p - 2), 4|(p - 3)$. But $p > 2$ is prime, thence $4 \not | p$. (1) How can you ...
1
vote
1answer
188 views

Ground plan of Backward direction (<=) - Let $p$ be an odd prime. Prove $x^{2} \equiv -1 \; (mod \, p)$ has a solution $\iff p\equiv 1 \; (mod 4)$

Apply the identity $p-i \equiv -i \mod p$ for $i=1, \ldots$ to the pink factors $ \begin{align} \color{seagreen}{ (p-1)! } = 1\times 2\times\cdots\times \dfrac{p-1}{2} & \times \quad ...
0
votes
1answer
40 views

If $q$ is a square modulo $m$ and modulo $n$, then $q$ is a square modulo $mn$

How do I show that if $q,m,n$ are integers, with $\gcd(m,n)=1$, then if $q$ is a square modulo $m$ and modulo $n$, then $q$ is a square modulo $mn$? I am assuming I should use the Chinese remainder ...
1
vote
1answer
53 views

Number of divisors of a perfect square

Given a number $n$ , let $m$ denote the number of divisors of $n$. Is there a way to express the number of divisors of $n^2$ explicitly through $m$ without using the powers of primes in the ...
1
vote
3answers
76 views

Trying to prove that there are no p and q such that $|\sqrt5 - p/q| < 1/(7q^2)$.

Like the title says, I'm having trouble proving that there are no integers p and q such that $|\sqrt5 - p/q| < 1/(7q^2)$. I was given the hint that $|(q\sqrt5 - p)(q\sqrt5 + p)| \geq 1$, but I ...
0
votes
2answers
97 views

Count subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively

Given a set of N elements, compute the number of subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively. Any hints would be appreciated. Thanks!
1
vote
2answers
69 views

How to prove that at least one of $a,b,c,d$ is not divisible by $ad-bc$ if $ad-bc>1$?

we have $ad-bc >1$ is it true that at least one of $a,b,c,d$ is not divisible by $ad-bc$ ? Thanks in advance. Example: $a=2$ , $b = 1$, $c = 2$, $d = 2$, $ad-bc = 2$ so $b$ is not divisible by ...
1
vote
1answer
119 views

Solution set to exponential in congruence

For which $n>0$ does $x^{2^n} \equiv 7 (mod \ 9)$ have a solution? It might be useful to start $x^{2^n} \equiv 16 (mod \ 9)$ but how should one proceed? Any hints would be appreciated. Thanks!
0
votes
1answer
74 views

Is 2(2k-1) is a perfect square for positive integer k?

For positive integer $k$, let $M = 2(2k-1)$, which of the following must be true? (a) $M$ is not a perfect square for any $k$. (b) There are infinitely many $k$ such that $M$ is a perfect square. ...
4
votes
1answer
3k views

How to determine whether a number can be written as a sum of two squares?

I know the following theorems: A number can be represented as a sum of two squares precisely when $N$ is of the form $n^2 \prod p_i$ where each $p_i$ is a prime congruent to 1 mod 4 If the equation ...
1
vote
1answer
173 views

How to use table of indices to solve a congruence?

I have trouble understanding the link between completing a table of indices to the base 3 modulo 17 (for example - which I can do just fine) and being asked to use the table to solve a congruence like ...
3
votes
1answer
67 views

Integer solutions to equations of the form $a^n+b^n+\cdots=c^n$

I shall refer to the number of terms on the left side of the equation as $m$. Suppose that all numbers in the equation are positive integers. I am wondering if anything is known about for which ...
0
votes
1answer
67 views

A form of Chinese remainder theorem

How can we solve equations of the form $c \equiv a \mod b$ for finding the c? Also, sometimes $c$ can be two different numbers, one negative and one positive, when is that possible and how does it ...
1
vote
2answers
111 views

Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\ $ for which $n?$

I found this question in my Math Challenge II Number Theory packet: Find all positive integers $n$ that satisfy $323|20^n+16^n-3^n-1$. I don't even have any idea how to approach this question. Any ...
0
votes
3answers
171 views

At least $p^2-p$ solutions to $x^2+y^2+z^2 \equiv 1 \mod p$

I'm trying to solve a graph theory problem that relies on for any prime $p$ there being at least $p^2-p$ solutions to $x^2+y^2+z^2 \equiv 1 \mod p$. I believe its true but my number theory is rusty ...
-1
votes
2answers
67 views

Find the natural numbers $n$ in which $n^2$ divides $584$? [duplicate]

I'm trying to find the natural numbers $n$ in which $n^2$ divides $584$ ? i tried all the ways i know but i get stuck.
0
votes
1answer
30 views

Questions on number operations

I took this practice text from University of Houston to prepare for the texes 4-8 math test. They do not show the correct answer if you get a question wrong. Can someone tell me the answer to these ...
1
vote
2answers
48 views

positive integer solutions of $y=\frac{5x}{3x-5}$

Any ideas on how to approach that problem besides brute-force? One solution is (x,y)=(2,10).
1
vote
1answer
65 views

How many different right triangles are possible with the shorter side of odd length?

I was trying to solve this problem but unable to figure it out completely. I thing number of was odd integer $n$ can be the side of right triangle is number of factor of $\frac{n^2}{2}$. Can some one ...
0
votes
0answers
192 views

Factor a big number by Pollard Rho method

How to factor $2^{2^8}+1$ by Pollard Rho algorithm? I have tried this question,but I have no clue. In order to use Pollard Rho, I should know some factor of this number right? But how can I find one?
2
votes
1answer
31 views

On the number of Hall divisors of an integer

A Hall divisor of an integer $n$ is a divisor $d$ of $n$ such that $d$ and $n/d$ are coprime. If $n$ is a positive integer, then $\varphi(n)$ is the number of integers $k$ in the range $1\leq k\leq ...