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

learn more… | top users | synonyms (1)

1
vote
4answers
177 views

How can I find the formula used to produce this number?

In a game, each character has different attributes with values to them. The attributes are things like Strength and Speed and are graded on a scale of 1-100. The game uses a formula to produce an ...
8
votes
1answer
137 views

Integer ordered pairs (x,y) satisfying $x^2 - y! = N$

This question arose by looking at a similar question, which has $N = 2001, 2013$. In it, my solution was that since we have a prime $p$ (in this case 3) which divides $N$ but $p^2$ doesn't, hence we ...
1
vote
2answers
387 views

Remainder when $26^{3008} + 3008^{26}$ is divided by $4$

I want to find the Remainder when $26^{3008} + 3008^{26}$ is divided by $4$. What should I do? Even though I've included the tag modular arithmetic I've very limited knowledge about it. How should I ...
3
votes
3answers
1k views

Use mathematical induction to prove that 9 divides $n^3 + (n + 1)^3 + (n + 2)^3$; Looking for explanation, I already have the solution.

I have the solution for this but I get lost at the end, here's what I have so far. basis $n = 0$; $9 \mid 0^3 + (0 + 1)^3 + (0 + 2)^2 ?$ $9 \mid 1 + 8$ = true Induction: Assume $n^3 + (n + ...
2
votes
1answer
52 views

Ratio Proportion question

What must be subtracted from each term of the ratio $3:7$ so that the ratio becomes $2:5?$ My attempt: Let two numbers be $3x$ and $7x.$ So, $\frac{3x-y}{7x-y}=\frac25 \implies 15x-5y=14x-2y ...
1
vote
3answers
167 views

Integer ordered pairs $(x,y)$ for which $x^2-y!$…

[1] Total no. of Integer ordered pairs $(x,y)$ for which $x^2-y! = 2001$ [2] Total no. of Integer ordered pairs $(x,y)$ for which $x^2-y! = 2013$ My Try:: (1) $x^2-y! = 2001\Rightarrow x^2 = ...
1
vote
0answers
52 views

How do I construct this multiplication table?

I was told to write out a multiplication table for $Z_3[\sqrt{3}]$. I'm not sure what that means... I'm used to just writing it out for $Z_3$
1
vote
0answers
121 views

is number theory a good place to start learning maths after a long break?

I haven't studied maths since my engineering degree some 15 years ago. At the time, I enjoyed maths and found it quite easy. However, now I feel that I have lost everything I learnt and I'm really ...
6
votes
3answers
453 views

$1^n +2^n + \cdots +(p-1)^n \mod p =$?

Calculate for every positive integer $n$ and for every prime $p$ the expression $$1^n +2^n + \cdots +(p-1)^n \mod p$$ I need your help for this. I don't know what to do, but I'll show you what I ...
1
vote
1answer
60 views

Quadratic Congruences Number Theory Question

Prove that every odd prime divisor of $n^2+100$ is of the form $12k+1$ or $12k+5$. I'm not sure how to do this.
2
votes
3answers
136 views

Demonstrate that if $ {\sqrt{a}} + {\sqrt{b}}\in\mathbb{Q}$ then $ {\sqrt{a}}\in\mathbb{Q}$ and ${\sqrt{b}}\in\mathbb{Q}$

$a,b\in\mathbb{Q}$ if $$ {\sqrt{a}} + {\sqrt{b}}\in\mathbb{Q}$$ demonstrates: $$ {\sqrt{a}}\in\mathbb{Q}$$ $${\sqrt{b}}\in\mathbb{Q}$$ I try to solve it with the property: If x, y ...
0
votes
0answers
28 views

Divisible polynomial and first term [duplicate]

How do I show that if $b^2+ab+1$ divides $a^2+ab+1$ for a, b are poaitive integers. Then $a=b$?
0
votes
1answer
55 views

Number theory in divisibility [closed]

Prove or disprove the following. Let $a_1,\ldots,a_r$ be positive even integers, and let $b_1,\ldots,b_s$ be positive integers. If $r\geq s+3$ and $a_i > b_j$ for all $i$ and $j$, then the quotient ...
1
vote
0answers
31 views

Are there any simple functions which map $\mathbb Z^n\to \mathbb Z\setminus \{k\}$ for given integer $k$?

Obviously, a function could be explicitly constructed as the set of all points in $\mathbb Z^n$ and what they are mapped to such that the given integer $k$ is not in the range. I am hoping to find a ...
2
votes
2answers
85 views

Number theory problem on numbers [closed]

Prove that if $n$ is divisible by $11$ and $n'$ is obtained from $n$ by inserting two identical digits between consecutive digits of $n$, then $n'$ is also divisible by $11$. For example, since $407$ ...
3
votes
2answers
93 views

What is the remainder of dividing $(116+17^{17})^{21}$ by $8$?

What is the remainder of dividing $(116+17^{17})^{21}$ by $8$? How to solve this? Solving the congruence (find the value of $a$) in $$(116+17^{17})^{21}\equiv a\pmod8$$ and how is this done?
2
votes
2answers
122 views

Number theory problem in induction

Without using the fundamental theorem of algebra (i.e. the prime factorization theorem), show directly that every positive integer is uniquely representable as the product of a non-negative power of ...
1
vote
3answers
152 views

What is the remainder of dividing $14^{256}$ by $17$?

What is the remainder of dividing $14^{256}$ by $17$? $$14^2\equiv 196\equiv 9 ...
5
votes
2answers
58 views

Image of an integer polynomial

How do I describe all integers that can be written in the form $$(x+y)^2+5x+3y$$ for some integers $x$ and $y$?
0
votes
2answers
102 views

How to find the remainder of $(2010^{1020} + 1020^{2010})$ divided by $3$

What is the remainder when $2010^{1020} + 1020^{2010}$ is divided by 3?
1
vote
1answer
163 views

ZFC-universe without non-standard natural numbers?

I assume, that we all have (beside any set-thoretic background) a good intuition, what "the usual natural numbers" are, although we seem not to be able to describe them precisely. So having said ...
4
votes
1answer
110 views

Prove that $1^2 3^2 5^2 \cdots (p-4)^2 (p-2)^2 \equiv (-1)^{(p+1)/2} \pmod p$.

Let $p$ be an odd prime number. Prove that $$1^2 3^2 5^2 \cdots (p-4)^2 (p-2)^2 \equiv (-1)^{(p+1)/2} \pmod p.$$ I know I can use Wilson's Theorem somehow. It would make sense if I could show that all ...
1
vote
3answers
49 views

If $a,p\in\mathbb{N}$ with $p$ prime, have to show that if $a²\equiv1\pmod p $, then $a\equiv1\pmod p$ or $a\equiv p-1\pmod p$

If $a,p\in\mathbb{N}$ with $p$ prime, have to show that if $a²\equiv1\pmod p $, then $a\equiv1\pmod p$ or $a\equiv p-1\pmod p$ I'm studying congruence, and I have no idea where to start this ...
2
votes
1answer
230 views

Number theory GCD word problem

An oil company has a contract to deliver 100,000 litres of gasoline. Their tankers can carry 2,400 litres, and they can attach one trailer carrying 2,200 litres to each tanker. All the tankers and ...
0
votes
1answer
34 views

If $a\equiv b\pmod m$ and $c+d\equiv 0\pmod m$ then $ac+bd\equiv 0\pmod m$ [duplicate]

If $a\equiv b\pmod m$ and $c+d\equiv 0\pmod m$ then $ac+bd\equiv 0\pmod m$. The response, posted below is correct??
3
votes
3answers
61 views

If $a+b\equiv0\pmod m$ and $c+d\equiv 0\pmod m$ then $ac\equiv bd\pmod m$. Demonstration.

If $a+b\equiv0\pmod m$ and $c+d\equiv 0\pmod m$ then $ac\equiv bd\pmod m$ How to show?$$$$ I tried $$a+b\equiv0\pmod m\Longrightarrow m\mid a+b\\c+d\equiv0\pmod m\Longrightarrow m\mid ...
1
vote
1answer
442 views

A GRE Math question

If a and b are positive integers such that the greatest common factor of $a^2b^2$ and $ab^3$ is 45, then which of the following could b equal? Select all such integers. ...
1
vote
0answers
219 views

Smallest positive integer divisible by and having digit sum equal to some 3-digit number.

Let $p,q,r$ be distinct digits among $1,2,4,6,8$, and consider the integer $pqr = 100p + 10q + r$. Let $N$ be the smallest positive integer that is divisible by $pqr$ and has digit sum equal to ...
1
vote
2answers
255 views

Quick way to find a number that, when multiplied by a given number, equals the outcome of a given modulo operation

I'm interested in solving the following equation: $$9x\equiv 58 \pmod{101}$$ Meaning taking $\pmod{101}$ of $9 \times$ some number $x$ will equal $58$. I know how to solve this using a table—in ...
0
votes
1answer
378 views

Subspaces of finite fields viewed as vector spaces on itself

How can I find the number of linear subspaces of dimensions 1 and 2 of the n- dimensional vector space $\mathbb{Z}^n_p$ over the field $\mathbb{Z}_p$?
1
vote
0answers
40 views

Number of solutions to $\sum_{k=1}^n\sigma_0(a_k)=N$

How many solutions are there to $$\sum_{k=1}^n\sigma_0(a_k)=N$$ , where $a_k<K$ and $N$ are positive integers? More precisely, I am looking for a closed form for $S(n,N)$, the number of solutions ...
0
votes
3answers
426 views

Mathematical induction prove that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ . [duplicate]

How can I use mathematical induction to prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a nonnegative integer?
0
votes
2answers
64 views

Euclid for polynomials [duplicate]

I have a question bout euclid polynomials. If $C(x) =x^4−1$ and $D(x) =x^3+x^2$ How do I find a polynomials $A(x)$ and $B(x)$ such that $A(x)C(x) +B(x)D(x) =x+1$ for all $x$?
1
vote
1answer
76 views

Legendre Symbols Number Theory

Calculate $\left(\frac{1}{73}\right)+\left(\frac{2}{73}\right)+\cdots+\left(\frac{72}{73}\right)$. I tried to find a pattern and got $1,1,1,1,-1,1,-1,1,1,-1,\ldots$ so I didn't see much of one. I am ...
1
vote
1answer
48 views

Decrypting a message?

I would like to ask for a little help about the following problem, i got stuck in it and have no idea how to proceed to get the answer which Wolfram Alpha gives (of course, i am not allowed to use the ...
3
votes
2answers
154 views

Olympiad level number theory

If $a + b + c + abc + ab + bc + ac$ = 1000 then $a + b + c=?$ . I don't know how to approach? Any hints welcome.
3
votes
1answer
465 views

Use induction to prove that $ 1 + \frac {1}{\sqrt{2}} + \frac {1}{\sqrt{3}} … + \frac {1}{\sqrt{n}} < 2\sqrt{n}$

Use induction to prove that $ 1 + \frac {1}{\sqrt{2}} + \frac {1}{\sqrt{3}} ... + \frac {1}{\sqrt{n}} < 2\sqrt{n} $ My attempt was as follows: Lets assume the inequality is true for n = k $S_k ...
2
votes
2answers
341 views

Using Carmichael function in RSA.

Given e and d as the encryption and decryption component respectively, textbook RSA has the property $ed\equiv 1\pmod {\phi(n)} $. The requirement is that suppose there is another function ...
3
votes
3answers
142 views

How to calculate $5^{3^{1000}}\bmod 101$?

I've just started a cryptography course, so i am not experienced at all how to calculate such big numbers. Clearly, i can't use a calculator, because the number is too big, so i have to calculate it ...
1
vote
2answers
420 views

Prove, for any positive integer $n$, that $n -3$ must be a multiple of $5$ if $n^3 -n -4$ is a multiple of $5$.

I had previously solved the problem of proving that $n^3-n-4$ must be a multiple of $5$, given that $n-3$ is a multiple of $5$. I did so by algebraically manipulating $n^3-n-4$ into: $$ ...
1
vote
1answer
96 views

Calculating elements of a particular order

$\newcommand{\ord}{\operatorname{ord}}$ To find all the elements in $(\mathbb Z_{10009}^*,\cdot)$ of order $72$ (without an exhaustive search), I have proceeded in the following manner : For a ...
3
votes
2answers
142 views

Finding Remainder Using Base $10$ or $5$

I am trying to find the remainder of $4^{220}$ when divided by $7$. $$4^{220}=2^{440}$$ Now had the question been what is the remainder of $2^{220}$ when divided by $10$, you would simply look ...
1
vote
1answer
62 views

Diophantus mathematics

Find a number whose subtraction from two given numbers (say, $9$ and $21$) allows both differences to be squares. Call the required number $9 - x^2$ so that the condition holds automatically.
1
vote
1answer
128 views

GCD = 1 and harmonic numbers, what is the exact asymptotic?

I am looking for the exact asymptotic for this partial sum: $$a(N) = \sum_{n=1}^{n=N}\sum_{k=1}_{GCD(n,k)=1}^{k=n*m} \frac{1}{k}$$ where $m$ is some integer $1,2,3,4,5,...$ My guess was that since ...
2
votes
2answers
65 views

Prove modular inequalities $ab + ac\le a(b+ac)$ and $(a+b)(a+c)\ge a+b(a+c)$

How to prove $$(a\cdot b)+(a\cdot c)\le a\cdot\big(b+(a\cdot c)\big)$$ and $$(a+b)\cdot(a+c)\ge a+\big(b\cdot(a+c)\big)\;?$$ I have tried this. Using distributive property, I think we can get ...
4
votes
3answers
311 views

Proving $\frac{1}{n+1} + \frac{1}{n+2}+\cdots+\frac{1}{2n} > \frac{13}{24}$ for $n>1,n\in\Bbb N$ by Induction

Proving $\frac{1}{n+1} + \frac{1}{n+2}+\cdots+\frac{1}{2n} > \frac{13}{24}$ for $n>1,n\in\Bbb N$ To solve it I used induction but it is leading me nowhere my attempt was as follows: Lets ...
6
votes
2answers
161 views

Is it sufficient to say that no odd divides an even number to prove it is a power of two?

A short preface: I'm reading the book Godel Esher Bach: Eternal Golden Braid, it describes a system which it calls Typographic Number Theory. There is a question in the book that asks to ...
3
votes
2answers
68 views

Infinitely many squares in a sequence.

In the sequence of integers $a, a+d, a + 2d, a + 3d, ... $ $a,d> 0$ How to prove that if one of the numbers is a square, than there are infinitely many squares in the sequence ?
0
votes
1answer
25 views

If $f(n)\geq\beta \sum_{i=0}^{n-1}f(i)$,then $f(n)?$

If $f(n)\geq\beta \sum_{i=0}^{n-1}f(i)$, then what can i say about $f(n)$ in terms of $f(1)$? I tried to find by taking equality and see how it progress, but i couldn't get. Any help is appreciated.
0
votes
1answer
794 views

Diophantine Equation Proof: Show that if $n=ab-a-b$, then there are no nonnegative solutions of $ax + by = n$

Let $a$ and $b$ be relatively prime positive integers and let $n$ be a positive integer. A solution $(x, y)$ of the linear diophantine equation $ax + by = n$ is nonnegative when both $x$ and $y$ are ...