File "SL-paper1.html"
Path: /IB QUESTIONBANKS/4 Fourth Edition - PAPER/HTML/Further Mathematics/Topic 6/SL-paper1html
File size: 29.25 KB
MIME-type: text/html
Charset: utf-8
<!DOCTYPE html>
<html>
<meta http-equiv="content-type" content="text/html;charset=utf-8">
<head>
<meta charset="utf-8">
<title>IB Questionbank</title>
<link rel="stylesheet" media="all" href="css/application-212ef6a30de2a281f3295db168f85ac1c6eb97815f52f785535f1adfaee1ef4f.css">
<link rel="stylesheet" media="print" href="css/print-6da094505524acaa25ea39a4dd5d6130a436fc43336c0bb89199951b860e98e9.css">
<script src="js/application-13d27c3a5846e837c0ce48b604dc257852658574909702fa21f9891f7bb643ed.js"></script>
<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML-full"></script>
<!--[if lt IE 9]>
<script src='https://cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv.min.js'></script>
<![endif]-->
<meta name="csrf-param" content="authenticity_token">
<meta name="csrf-token" content="iHF+M3VlRFlNEehLVICYgYgqiF8jIFlzjGNjIwqOK9cFH3ZNdavBJrv/YQpz8vcspoICfQcFHW8kSsHnJsBwfg==">
<link href="favicon.ico" rel="shortcut icon">
</head>
<body class="teacher questions-show">
<div class="navbar navbar-fixed-top">
<div class="navbar-inner">
<div class="container">
<div class="brand">
<div class="inner"><a href="http://ibo.org/">ibo.org</a></div>
</div>
<ul class="nav">
<li>
<a href="../../index.html">Home</a>
</li>
<li class="active dropdown">
<a class="dropdown-toggle" data-toggle="dropdown" href="#">
Questionbanks
<b class="caret"></b>
</a><ul class="dropdown-menu">
<li>
<a href="../../geography.html" target="_blank">DP Geography</a>
</li>
<li>
<a href="../../physics.html" target="_blank">DP Physics</a>
</li>
<li>
<a href="../../chemistry.html" target="_blank">DP Chemistry</a>
</li>
<li>
<a href="../../biology.html" target="_blank">DP Biology</a>
</li>
<li>
<a href="../../furtherMath.html" target="_blank">DP Further Mathematics HL</a>
</li>
<li>
<a href="../../mathHL.html" target="_blank">DP Mathematics HL</a>
</li>
<li>
<a href="../../mathSL.html" target="_blank">DP Mathematics SL</a>
</li>
<li>
<a href="../../mathStudies.html" target="_blank">DP Mathematical Studies</a>
</li>
</ul></li>
<!-- - if current_user.is_language_services? && !current_user.is_publishing? -->
<!-- %li= link_to "Language services", tolk_path -->
</ul>
<ul class="nav pull-right">
<li>
<a href="https://06082010.xyz">IB Documents (2) Team</a>
</li></ul>
</div>
</div>
</div>
<div class="page-content container">
<div class="row">
<div class="span24">
</div>
</div>
<div class="page-header">
<div class="row">
<div class="span16">
<p class="back-to-list">
</p>
</div>
<div class="span8" style="margin: 0 0 -19px 0;">
<img style="width: 100%;" class="qb_logo" src="images/logo.jpg" alt="Ib qb 46 logo">
</div>
</div>
</div><h2>SL Paper 1</h2><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Show that \({2^n} \equiv {( - 1)^n}(\bmod 3)\)<span class="s1">, where \(n \in \mathbb{N}\).</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1"><span class="s1">Hence show that an integer is divisible by 3 if and only if the difference between the </span>sum of its binary (base 2) digits in even-numbered positions and the sum of its binary digits in odd-numbered positions is divisible by 3.</p>
<div class="marks">[3]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Express the hexadecimal (base 16) number \({\text{ABB}}{{\text{A}}_{{\text{16}}}}\) <span class="s1">in binary.</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="specification">
<p class="p1">Consider the recurrence relation \({H_{n + 1}} = 2{H_n} + 1,{\text{ }}n \in {\mathbb{Z}^ + }\) where \({H_1} = 1\).</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Find \({H_2}\), \({H_3}\) and \({H_4}\).</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Conjecture a formula for \({H_n}\) <span class="s1">in terms of \(n\), for \(n \in {\mathbb{Z}^ + }\).</span></p>
<div class="marks">[1]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Prove by mathematical induction that your formula is valid for all \(n \in {\mathbb{Z}^ + }\).</p>
<div class="marks">[5]</div>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="specification">
<p class="p1">Consider the Diophantine equation \(7x - 5y = 1,{\text{ }}x,{\text{ }}y \in \mathbb{Z}\).</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Find the general solution to this equation.</p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Hence find the solution with minimum positive value of \(xy\).</p>
<div class="marks">[2]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Find the solution satisfying \(xy = 2014\).</p>
<div class="marks">[3]</div>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>A number written in base 5 is 4303. Find this as a number written in base 10.</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>1000 is a number written in base 10. Find this as a number written in base 7.</p>
<div class="marks">[5]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p>The simple connected planar graph \(J\) has the following adjacency table.</p>
<p style="text-align: center;"><img src="images/Schermafbeelding_2017-08-17_om_13.09.29.png" alt="M17/5/FURMA/HP1/ENG/TZ0/11"></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Without attempting to draw \(J\), verify that <em>J </em>satisfies the handshaking lemma;</p>
<div class="marks">[1]</div>
<div class="question_part_label">a.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Without attempting to draw \(J\), determine the number of faces in \(J\).</p>
<div class="marks">[3]</div>
<div class="question_part_label">a.ii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>The vertices D and G are joined by a single edge to form the graph \(K\). Show that \(K\) is not planar.</p>
<div class="marks">[3]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Explain why a graph containing a cycle of length three cannot be bipartite. </p>
<div class="marks">[3]</div>
<div class="question_part_label">c.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Hence by finding a cycle of length three, show that the complement of \(K\) is not bipartite.</p>
<div class="marks">[2]</div>
<div class="question_part_label">c.ii.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Use the Euclidean algorithm to find the greatest common divisor of 74 and 383.</p>
<div class="marks">[4]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Hence find integers <em>s</em> and <em>t</em> such that 74<em>s</em> + 383<em>t</em> = 1.</p>
<div class="marks">[5]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Given that \(a \equiv b(\bmod p)\) , show that \({a^n} \equiv {b^n}(\bmod p)\) for all \(n \in {\mathbb{Z}^ + }\) .</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Show that \({29^{13}} + {13^{29}}\) is exactly divisible by \(7\).</span></p>
<div class="marks">[5]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Find the general solution to the Diophantine equation \(3x + 5y = 7\).</p>
<div class="marks">[5]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Find the values of \(x\) and \(y\) satisfying the equation for which \(x\) <span class="s1">has the smallest positive integer value greater than \(50\)</span>.</p>
<div class="marks">[2]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Consider the linear congruence \(ax \equiv b(\bmod p)\) where \(a,{\text{ }}b \in {\mathbb{Z}^ + },{\text{ }}p\) is a prime and \(\gcd (a,{\text{ }}p) = 1\). Using Fermat’s little theorem, show that \(x \equiv {a^{p - 2}}b(\bmod p)\).</p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><strong>Hence </strong>find the smallest value of \(x\) greater than 100 satisfying the linear congruence \(3x \equiv 13(\bmod 19)\).</p>
<div class="marks">[4]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Use the Euclidean algorithm to find \(\gcd (162,{\text{ }}5982)\).</p>
<div class="marks">[4]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1"><span class="s1">The relation \(R\) </span>is defined on \({\mathbb{Z}^ + }\) by \(nRm\) if and only if \(\gcd (n,{\text{ }}m) = 2\).</p>
<p class="p1">(i) <span class="Apple-converted-space"> </span>By finding counterexamples show that \(R\) is neither reflexive nor transitive.</p>
<p class="p1">(ii) <span class="Apple-converted-space"> </span>Write down the set of solutions of \(nR6\).</p>
<div class="marks">[7]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Express the number \(47502\) as a product of its prime factors.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">The positive integers \(M\) , \(N\) are such that \(\gcd (M,N) = 63\) and </span><span style="font-family: times new roman,times; font-size: medium;">\(lcm(M,N) = 47502\) . Given that \(M\) is even and \(M < N\) , find the two possible </span><span style="font-family: times new roman,times; font-size: medium;">pairs of values for \(M\) , \(N\) .</span></p>
<div class="marks">[5]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Solve the recurrence relation \({u_n} = 4{u_{n - 1}} - 4{u_{n - 2}}\) given that \({u_0} = {u_1} = 1\).</p>
<div class="marks">[6]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Consider \({v_n}\) which satisfies the recurrence relation \(2{v_n} = 7{v_{n - 1}} - 3{v_{n - 2}}\) subject to the initial conditions \({v_0} = {v_1} = 1\).</p>
<p>Prove by using strong induction that \({v_n} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^n} + \frac{1}{5}{\left( 3 \right)^n}\) for \(n \in \mathbb{N}\).</p>
<div class="marks">[9]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question">
<p><span style="font-family: times new roman,times; font-size: medium;">Prove that \(3k + 2\) and \(5k + 3\) , \(k \in \mathbb{Z}\) are relatively prime.</span></p>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Prove that the number \(14 641\) is the fourth power of an integer in any base greater </span><span style="font-family: times new roman,times; font-size: medium;">than \(6\).</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">For \(a,b \in \mathbb{Z}\)</span><span style="font-family: times new roman,times; font-size: medium;"> the relation \(aRb\) is defined if and only if \(\frac{a}{b} = {2^k}\) </span><span style="font-family: times new roman,times; font-size: medium;">, \(k \in \mathbb{Z}\)</span><span style="font-family: times new roman,times; font-size: medium;"> .</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (i) Prove that \(R\) is an equivalence relation.</span></p>
<p style="margin-left: 30px;"><span style="font-family: times new roman,times; font-size: medium;"> (ii) List the equivalence classes of \(R\) on the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Using mathematical induction or otherwise, prove that the number \({(1020)_n}\) , </span><span style="font-family: times new roman,times; font-size: medium;">that is the number \(1020\) written with base \(n\) , is divisible by \(3\) for all values of \(n\) </span><span style="font-family: times new roman,times; font-size: medium;">greater than \(2\).</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Explain briefly why the case \(n = 2\) has to be excluded.</span></p>
<div class="marks">[1]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Prove that if \({\rm{gcd}}(a,b) = 1\) and \({\rm{gcd}}(a,c) = 1\) , then \({\rm{gcd}}(a,bc) = 1\) .</span></p>
<div class="marks">[5]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) A simple graph has <strong><em>e</em></strong> edges and <strong><em>v</em></strong> vertices, where \(v > 2\) . Prove that if all </span><span style="font-family: times new roman,times; font-size: medium;">the vertices have degree at least <strong><em>k</em></strong> , then \(2e \ge kv\) .</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) <strong>Hence</strong> prove that every planar graph has at least one vertex of degree less </span><span style="font-family: times new roman,times; font-size: medium;">than 6.</span></p>
<div class="marks">[6]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p><span style="font-family: times new roman,times; font-size: medium;"><img style="display: block; margin-left: auto; margin-right: auto;" src="images/thor.png" alt></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">The above diagram shows the weighted graph \(G\).</span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Determine whether or not \(G\) is bipartite.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Write down the adjacency matrix for \(G\).</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Find the number of distinct walks of length \(4\) beginning and ending at A.</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Use the Euclidean Algorithm to show that \(275\) and \(378\) are relatively prime.</span></p>
<div class="marks">[5]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Find the general solution to the diophantine equation \(275x + 378y = 1\) .</span></p>
<div class="marks">[7]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p>An integer \(N\) given in base \(r\), can be expressed in base \(s\) in the form</p>
<p>\(N = {a_0} + {a_1}s + {a_2}{s^2} + {a_3}{s^3} + \ldots \) where \({a_0},{\text{ }}{a_1},{\text{ }}{a_2},{\text{ }} \ldots \in \{ 0,{\text{ }}1,{\text{ }}2,{\text{ }} \ldots ,{\text{ }}s - 1\} \).</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">In base \(5\)<span class="s1"> </span>an integer is written \(1031\)<span class="s1">. </span>Express this integer in base \(10\).</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Given that \(N = 365,{\text{ }}r = 10\) and \(s = 7\) find the values of \({a_0},{\text{ }}{a_1},{\text{ }}{a_2},{\text{ }} \ldots \).</p>
<div class="marks">[2]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">(i) <span class="Apple-converted-space"> </span>Given that \(N = 899,{\text{ }}r = 10\) and \(s = 12\) find the values of \({a_0},{\text{ }}{a_1},{\text{ }}{a_2},{\text{ }} \ldots \)</p>
<p class="p2">(ii) <span class="Apple-converted-space"> </span>Hence write down the integer in base \(12\), which is equivalent to \(899\) in base \(10\)<span class="s1">.</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Show that \(121\)<span class="s1"> </span>is always a square number in any base greater than \(2\).</p>
<div class="marks">[3]</div>
<div class="question_part_label">d.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Use the Euclidean algorithm to find gcd(\(6750\), \(144\)) .</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Express your answer in the form \(6750r + 144s\) where <strong><em>r</em></strong> , \(s \in \mathbb{Z}\) .</span></p>
<div class="marks">[6]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Consider the base \(15\) number CBA, where A, B, C represent respectively the </span><span style="font-family: times new roman,times; font-size: medium;">digits ten, eleven, twelve.</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (i) Write this number in base \(10\).</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (ii) Hence express this number as a product of prime factors, writing the factors </span><span style="font-family: times new roman,times; font-size: medium;">in base 4.</span></p>
<div class="marks">[6]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Sum the series \(\sum\limits_{r = 0}^\infty {{x^r}} \) .</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) <strong>Hence</strong>, using sigma notation, deduce a series for</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (a) \(\frac{1}{{1 + {x^2}}}\) ;</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (b) \(\arctan x\) ;</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (c) \(\frac{\pi }{6}\) .</span></p>
<div class="marks">[11]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Show that \(\sum\limits_{n = 1}^{100} {n! \equiv 3(\bmod 15)} \) .</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="specification">
<p><span style="font-family: times new roman,times; font-size: medium;">The positive integer \(N\) is represented by \(4064\) in base \(b\) and \(2612\) in base \(b + 1\) .</span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Determine the value of \(b\) .</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Find the representation of \(N\)</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (i) in base \(10\);</span></p>
<p style="margin-left: 30px;"><span style="font-family: times new roman,times; font-size: medium;"> (ii) in base \(12\).</span></p>
<div class="marks">[6]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question">
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">Find the positive square root of the base 7 number \({(551662)_7}\), giving your answer as a base 7 number.</span></p>
</div>
<br><hr><br><div class="question">
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(a) Show that the solution to the linear congruence \(ax \equiv b(\bmod p)\), where \(a,{\text{ }}x,{\text{ }}b,{\text{ }}p \in {\mathbb{Z}^ + },{\text{ }}p\) is prime and \(a\), \(p\) are relatively prime, is given by \(x \equiv {a^{p - 2}}b(\bmod p)\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(b) Consider the congruences</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;"> \(7x \equiv 13(\bmod 19)\)</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;"> \(2x \equiv 1(\bmod 7)\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(i) Use the result in (a) to solve the first congruence, giving your answer in the form \(x \equiv k(\bmod 19)\) where \(1 \leqslant k \leqslant 18\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) Find the set of integers which satisfy both congruences simultaneously.</span></p>
</div>
<br><hr><br><div class="question">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Given that \({n^2} + 2n + 3 \equiv N(\bmod 8)\) , where \(n \in {\mathbb{Z}^ + }\) and \(0 \le N \le 7\) , prove that \(N\) can </span><span style="font-family: times new roman,times; font-size: medium;">take one of only three possible values.</span></p>
</div>
<br><hr><br><div class="question">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">A sequence \(\left\{ {{u_n}} \right\}\) satisfies the recurrence relation \({u_{n + 2}} = 2{u_{n + 1}} - 5{u_n}\) , \(n \in \mathbb{N}\) . Obtain an </span><span style="font-family: times new roman,times; font-size: medium;">expression for \({u_n}\) in terms of <strong><em>n</em></strong> given that \({u_0} = 0\) and \({u_1} = 1\) .</span></p>
</div>
<br><hr><br><div class="specification">
<p><span style="font-family: times new roman,times; font-size: medium;">The figure below shows the graph <strong><em>G</em></strong> .</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><br><img src="images/chick.png" alt></span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<address><span style="font-family: times new roman,times; font-size: medium;">(i) Write down the adjacency matrix for \(G\) .</span></address>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Find the number of walks of length \(4\) beginning and ending at B.</span></p>
<div class="marks">[5]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Draw \(G'\), the complement of \(G\) .</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) Write down the degrees of all the vertices of \(G\) and all the vertices of \(G'\).</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(iii) Hence, or otherwise, determine whether or not \(G\) and \(G'\) are isomorphic.</span></p>
<div class="marks">[6]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p class="p1">A simple graph \(G\) is represented by the following adjacency table.</p>
<p class="p1" style="text-align: center;"><img src="images/Schermafbeelding_2015-12-15_om_07.29.58.png" alt></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Draw the simple graph \(G\).</p>
<div class="marks">[1]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Explain why \(G\) does not contain an Eulerian circuit.</p>
<div class="marks">[1]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Show that \(G\) has a Hamiltonian cycle.</p>
<div class="marks">[2]</div>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">State whether or not \(G\) is planar, giving a reason for your answer.</p>
<div class="marks">[2]</div>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">State whether or not the simple graph \(G\) is bipartite, giving a reason for your answer.</p>
<div class="marks">[2]</div>
<div class="question_part_label">e.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Draw the complement \(G'\) of \(G\).</p>
<div class="marks">[2]</div>
<div class="question_part_label">f.</div>
</div>
<br><hr><br>