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

learn more… | top users | synonyms (1)

2
votes
2answers
46 views

Finding the solutions of $x^2\equiv 9 \pmod {256}$.

Find the solutions of $x^2\equiv 9 \pmod {256}$. I try to follow an algorithm shown us in class, but I am having troubles doing so. First I have to check how many solutions there are. Since $9\equiv 1 ...
-4
votes
0answers
19 views

How to find two numbers given their sum of squares, HCF and LCM? [on hold]

if sum of squares of two numbers are 2754,HCF is 9,LCM is 135...what are the numbers?
-1
votes
3answers
32 views

How to find two numbers given their difference, HCF and LCM? [on hold]

The difference of two numbers is 14. Their LCM and HCF are 441 and 7 respectively. Find the numbers. Any shortcuts please. Thanks in advance.
2
votes
1answer
23 views

Proof by induction from Spivak's calculus ch 2- 3b

I was cracking my head over the following proof (by induction) from Spivak's calculus. Givens: $ \binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k} $ and $ n \ge k $ Task: Proof by induction that $ ...
3
votes
2answers
24 views

Let $X$ be a set of primes $p$ so that $5^{p^2}+1 \equiv 0 \pmod {p^2}$ Which of these sets is $X$ equal to?

$5^{p^2}+1\equiv 0\pmod {p^2}$ $1.$ $\emptyset $ $2.$ {$3$} $3.$ All primes of the form $4k+3$ $4.$ All primes except $2$ and $5$ $5.$ All primes This one is pretty easy to get right through the ...
0
votes
0answers
9 views

Number of number in range $(l, r)$ satisfying XOR constarint

Here's a questions that's been bugging for some time now: Define the set $S_n = \{k \oplus (k + n)\mid k \in \Bbb Z, k ≥ 0\}$ (here, $\oplus$ is bitwise exclusive OR). To put it another way, $x$ ...
1
vote
2answers
66 views

Why is $ {n\choose k} \equiv 0 \pmod n$ if $n$ is prime? [duplicate]

For all $n>k$, why is: $$ {n\choose k} \equiv 0 \pmod n$$ if $n$ is prime? Any hints anyone? I am really puzzled.
0
votes
1answer
27 views

Legendre symbol, a theoretical question.

I need to show that if $p$ is a prime number of the form $p=4m+1$, then for any divisor $d$ of $m$: $$\left(\frac{d}{p} \right) = 1$$ where $\left(\frac{d}{p} \right)$ is the Legendre symbol. My ...
0
votes
2answers
40 views

Show that the equation $x^2\equiv a \pmod n$ is solvable $\iff$ $a^{\phi (n)\over 2}\equiv 1\pmod n$.

Let $n> 2$ be an integer such that $(\Bbb{Z}/n\Bbb{Z})^*$ has a primitive root. Show that the equation $x^2\equiv a \pmod n$ is solvable $\iff$ $a^{\phi (n)\over 2}\equiv 1\pmod n$. I thought I ...
0
votes
1answer
21 views

Let $n \in \mathbb{N}$ and consider the commutative ring $\mathbb{Z}_n$. Let $a \in \{1,2,…,n-1,n\}$…

Let $n \in \mathbb{N}$ and consider the commutative ring $\mathbb{Z}_n$. Let $a \in \{1,2,...,n-1,n\}$. Suppose $a$ is coprime to $n$ then prove $\bar{a} \in \mathbb{Z}_n$ is a unit. Note ...
1
vote
2answers
36 views

A set of numbers

Problem: Let $E(x)$ be the number defined by the following expression \begin{equation*} E(x)=\sqrt[3]\frac{x^3-3x+(x^2-1)\sqrt{x^2-4}}{2}+\sqrt[3]\frac{x^3-3x-(x^2-1)\sqrt{x^2-4}}{2} \end{equation*} ...
3
votes
1answer
18 views

How to proceed with Euclidean algorithm for finding greatest common divisor of two polynomials.

I am trying to find \begin{equation*} gcd(x^4-x^3-4x^2-x+5,x^2+x-2). \end{equation*} I have done the first step of long division and found. \begin{equation*} x^4-x^3-4x^2-x+5=(x^2-2x)(x^2+x-2)-5x+5 ...
3
votes
1answer
21 views

The necessary and sufficient condition for a regular n-gon to be constructible by ruler and compass.

I have a problem concerning the necessary and sufficient condition for a regular n-gon to be constructible by ruler and compass. $\bf My$ $\bf question:$ For a given positive integer $n$, how can we ...
0
votes
0answers
26 views

Prove: If $p \in \mathbb{N}$, $p$ is prime and $p\mid ab$ then $p\mid a$ or $p\mid b$. [duplicate]

Theorem 1. If $p \in \mathbb{N}$, $p$ is prime and $p\mid ab$ then $p\mid a$ or $p\mid b$. I am stuck on this proof here is what I have done so far: Proof of Thm 1. $p\mid ab \implies ...
0
votes
2answers
37 views

Find the number of possible values of $a$

Positive integers $a, b, c$, and $d$ satisfy $a > b > c > d, a + b + c + d = 2010$, and $a^2 − b^2 + c^2 − d^2 = 2010$. Find the number of possible values of $a.$ Obviously, factoring, ...
1
vote
1answer
22 views

A question about $\gcd$ and divisibility

Let $\sigma$ be the classical sum-of-divisors function. Suppose that I have the following equations: $$2n^2 - \sigma(n^2) = \frac{\sigma(n^2)}{q^k}\cdot{\sigma(q^{k-1})}$$ $$2n^2 - \sigma(n^2) = ...
3
votes
1answer
22 views

What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$?

Let $\sigma$ denote the classical sum-of-divisors function. What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$? Update: I have transferred the transcript of my attempt to an actual answer to this MSE ...
0
votes
1answer
15 views

How many rows & columns do 1,028 equal spaces create…

I have a board that is 17.5" wide and 67" long. I need to divide this board into 1,028 equal spaces. How many rows and how many columns will this equate to?
5
votes
1answer
52 views

How can I prove the Carmichael theorem

I am trying to prove that these two definitions of Carmichael function are equivalent. I am using this definition of Carmichael function: $\lambda(n)$ is the smallest integer such that ...
1
vote
4answers
63 views

$6^{66}\equiv r \pmod {66}$

The answer doesn't need to be exact, the possible answers to the exercise are "between 30 and 40", "from 50 to 66" or something akin to that. I've no idea how to solve this. Previous problems of this ...
0
votes
2answers
39 views

Prove: $\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$ [duplicate]

I'm trying to prove the following statement: $$\forall_{a,b\in\Bbb{N^{+}}}\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$$ As for now I managed to prove that $n^{\gcd(a,b)}-1$ divdes $n^a-1$ and $n^b-1$: Without ...
0
votes
1answer
26 views

General question on notations when dealing multiplicative and additive modulo

One of the property for the requirement for a set to be a group is associativity. Under ordinary multiplication: $\large{a(bc)=(ab)c}$ Under ordinary addition: $\large{a+(b+c)=(a+b)+c}$ What ...
5
votes
1answer
38 views

Remainders of quadratic trinomial

The problem is to determine, whether there exist a quadratic trinomial $f(x) = ax^2 + bx +c$ with integer coefficients (with $a$ not a multiple of 2014), such that the numbers $\ f(1), \ f(2),\, ...
1
vote
0answers
27 views

Prove that one eight of Gauss circle problem counts integer sided acute triangles with largest side n.

In the OEIS there is the sequence A247588 starting: 1, 2, 3, 5, 6, 8, 11, 13, 15, 17, 21, 25, 27,... It has the name "Number of integer sided acute triangles with largest side n." Let $a(n)$ be that ...
0
votes
1answer
31 views

Show that the set $\{1,2,\ldots, n-1\}$ is a group under $\bmod n$ IFF $n$ is prime.

So I need to show that this set, together with the operation of multiplication mod $n$, is a group if, and only if, $n$ is prime. What would be the best way to proceed? proof by contradiction? (i.e. ...
4
votes
2answers
40 views

What are statements about the natural numbers where induction is impossible or unnecessary to prove?

I'm looking for statements like "for all natural numbers, ____" where induction would be impossible or unnecessarily complicated. This is for pedagogical reasons. When students first learn induction, ...
0
votes
2answers
50 views

solve $b^2c-a^2=d^3$ with some conditions.

Solve $b^2 c-a^2=d^3$ Conditions $b^2c>a^2$,  $b$>0, $c$>0,  $a$, $b$, $c$, $d$ are rational number. Example Solution $a=108$, $b=12$, $c=849$, $d=48$ Is Solving this equation impossible?
-1
votes
2answers
35 views

Difference between $A \equiv B \pmod {n}$ and $A \pmod {n}$

In terms of definition and ideas, what is the difference between saying $$A \equiv B \pmod n$$ and $$A \pmod n$$?
2
votes
2answers
67 views

Find the smallest number divisible by $204$ the digits of which sum to $204$

The problem asks us to find the smallest number divisible by $204$, with sum of its digits equal to $204$. I totally don't know what to use here. I would be thankful for any hint that would enable ...
2
votes
3answers
60 views

Evaluate $7^{8^9}\mod 100$

I'm preparing myself for discrete math exam and here's one of the preparation problems: Evaluate $$7^{8^9}\mod 100$$ Here's my solution: $7^2\equiv49 \mod 100\implies (7^2)^2\equiv49^2=2401\equiv ...
2
votes
2answers
61 views

Properties of Euler's phi function [on hold]

If $\phi(n) =n-2$ then $n=4$. I need a hint to prove this statement. "This is my first Number Theory course."
1
vote
3answers
35 views

If $n$ is a natural number and $n$ is a $4th$ power and a $5th$ power prove it is a $20th$ power.

If $n$ is a natural number and $n$ is a $4th$ power and a $5th$ power prove it is a $20th$ power. (Hint: Use fundamental theorem of arithmetic). I can't do this problem and am looking for ...
3
votes
2answers
118 views

Solving the Diophantine equation $x^n-y^n=1001$

For all $n \in \mathbb{N}$, solve the Diophantine equation $x^n-y^n=1001$, where $x,y \in \mathbb{N}$. The cases $n=1,2$ are trivial ones. But for $n>2$ I can't find any solutions. How could I ...
1
vote
1answer
18 views

How does the fundamental theorem of arithmetic / primality tests apply to GCDs?

I've been asked to calculate gcd(1962,1524) which I found to be 6. Now I'm asked to 'Verify your answer using primality tests and the fundamental theorem of arithmetic I'm struggling to see how I ...
1
vote
1answer
24 views

Properties of Jacobi symbol

Let $\left(\frac{a}{n}\right) $ be Jacobi symbol . It is well known that Jacobi symbol for $a=-1$ and $a=2$ satisfies the following: $\left(\frac{-1}{n}\right) = \begin{cases} 1, & \text{if } n ...
2
votes
2answers
31 views

How to establish the distributive property of sum notation

Establish the following property of sum notation: $$\sum_{i=1}^{n}(a_i+b_i) = \sum_{i=1}^{n}a_i + \sum_{i=1}^{n}b_i$$ I have tried in two ways. My first try uses recursive induction: ...
1
vote
1answer
43 views

Finding the order of 3 modulo 242

I know from Euler's theorem that \begin{equation*} 3^{110} \equiv 1\mod 242 \end{equation*} because \begin{equation*} \phi(242) = 110. \end{equation*} However to find the order of $3$, I need to find ...
0
votes
2answers
33 views

How to find kth smallest value of a linear equation

Here's a question that was asked in IOITC 2009 India. Even though it should have a solution related to algorithms, yet I post it here as it is pretty "number-theoretic". Indraneel loves posing ...
0
votes
1answer
21 views

Arithmetic modulo $n$ when $n>a$

$r=a \pmod n$ can be rewritten as $a = qn + r$ where $a$ and $n$ are positive and non-zero integers and $q$ is a unique integer. When solving for $a \pmod n$ such that $a$ is greater than $n$, it is ...
-3
votes
1answer
33 views

Revised proof for the set of positive irrational numbers closed under multiplication* [on hold]

The set S of positive irrational number is closed under multiplication (denote *) if the product of an ordered pair of element of S is also an element of set S. To show that the set S is not closed, ...
0
votes
5answers
82 views

A better proof for the set of irrational number not closed under ordinary multiplication.

A positive irrational number $$q$$ is by definition a real number than cannot be expressed as a ratio of $2$ integers. To show that the set of irrational number is not closed under ordinary ...
0
votes
1answer
29 views

Show that the set $\mathbb{Q}^+$ is a group under ordinary multiplication

To be a group, a set with a binary operation has to satisfy all four of the group axioms. My problem is with closure as each time I am unsure if my proof suffices. The set of positive rational numbers ...
4
votes
3answers
151 views

Numbers with 2015

I like to build math problems; to solve the one below I should first find a certain square and use it in my solution. I would want to know if anyone can solve this problem otherwise. Thanks. ...
0
votes
1answer
23 views

Stuck on proving two quite simple results using modular arithmetic and factors.

Hello I'm trying to do two problems but can't seem to get the proofs myself, any help is appreciated. I know the definitions of congruence, definition of a factor and Bezout's lemma I've tried using ...
0
votes
3answers
27 views

If $A|B$ and $B|A$ then prove $A=\pm B$ [duplicate]

If $A|B$ and $B|A$ then prove $A=\pm B$ So far I have $A|B \iff AX=B$ and $B|A \iff BY=A$ with $X,Y \in \mathbb{Z}$ Not sure how to finish, any help.
2
votes
2answers
49 views

Prove that $a^{p^2}\equiv a^p\pmod{p^2}$ for every $a\in\mathbb{Z}$

Question: Prove that $a^{p^2}\equiv a^p\pmod{p^2}$ for every $a\in\mathbb{Z}$ First note that when $p$ is prime and $1\leq r\leq p-1$ the binomial coefficient $$\binom{p}{r}=\frac{p!}{r!(p-r)!}$$ is ...
2
votes
0answers
52 views

can you help me to solve this equation in antural numbers set?

Can you help me find the natural solutions of $$2^x+3^y=5^z$$ or can you introduce a book that talk about these equations?
0
votes
2answers
44 views

Confusion with $O$ function

I read this identity in lecture notes and need help understand ing the $O$ function $$\sum_{1\leq d\leq x}\mu(d)\cdot \frac{1}{2}\left\lfloor\frac xd\right\rfloor\left(\left\lfloor\frac ...
0
votes
2answers
23 views

Finding the GCD of two polynomials.

Hello I'm trying to find the GCD of these two polynomials: $$X^4-X^3-4X^2-X+5$$ $$X^2+X-2$$ And then I want to express the GCD of these two polynomials in terms of themselves multiplied by other ...
3
votes
2answers
41 views

$\forall n\ /\ \not\exists$ {primitive roots modulo n}: if $\ Max(ord_n(k))+1 \mid n\ $ then $\ Max(ord_n(k))+1\ $ is prime?

When a number $n$ does not have primitive roots modulo n, $Pr(n)$, it is possible to generate the set $M$ of those numbers $m$ whose order $ord_n(m)$ is the maximum multiplicative order of $k$ in ...